1964. 给灵梦修宽带(打黑工)

由于出题人刚到此地,于是想去拜访灵梦了解一下情况。

在交了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),此时 ba,c 直接连接,但不认为 a,c 是直接连接的。

请注意本题空间限制为 32MB。

来源

2023 SCNUCPC 网络赛 (重现)

登录以提交代码。
单点时限 1 秒
内存限制 32 MB
提交 7
通过 4