由于出题人刚到此地,于是想去拜访灵梦了解一下情况。
在交了10万門的奉纳后终于进到了博丽神社里,此时出题人才意识到幻想乡是有网的,灵梦正在修理114514根网线。
为了快点了解到这个世界的信息,出题人决定帮灵梦修网,不过这里的网络很贵,访问任何站点都要交钱。
在数轴上有 n 个点,第 i (编号从 1 开始)个点的坐标是 a_i,其颜色为黑色或白色其一。你可以选择两个点 u,v(1\le u < v\le n),将其连接,代价为 |a_u-a_v|。最终你需要让每个点直接连接至少一个与它不同颜色的点,请输出最小代价。
输入
输入一行一个整数 n(2\le n\le5\times10^3)。
接下来输入一行 n 个整数,第 i 个整数为 a_i(0\le a_i\le10^5)。
接下来输入一行 n 个整数,第 i 个整数为 b_i(0\le b_i\le 1),若 b_i=0 则该点为白色,否则为黑色。
输入保证有至少一个黑点和至少一个白点。
输出
输出一行一个整数,代表最小代价。
样例
标准输入 复制文本 |
3 1 4 5 1 0 1 |
标准输出 复制文本 |
4 |
标准输入 复制文本 |
7 1 2 3 6 8 9 5 1 0 1 0 1 0 1 |
标准输出 复制文本 |
4 |
标准输入 复制文本 |
2 6 6 1 0 |
标准输出 复制文本 |
0 |
提示
对样例,连接 (1,4),(4,5),总代价为 |1-4|+|4-5|=4。
注意假设连接了 (a,b),(b,c),此时 b 与 a,c 直接连接,但不认为 a,c 是直接连接的。
请注意本题空间限制为 32MB。
来源
2023 SCNUCPC 网络赛 (重现)