2060. 归零行动(30分)

"宇宙是一座黑暗森林,每个文明都是带枪的猎人。如果发现了别的生命,能做的只有一件事:开枪消灭..."

在黑暗森林的宇宙里,分布着 n 颗星星,每颗星星都有寿命 a 和自己专属的孤独值 b 。看着这些孤单的星星,归零者决定用法力把所有的星星连接在一起,但是归零者的魔法需要遵循下面的物理规律:

  • 每次只能连接两颗星星,需要耗费的法力为两颗星星的孤独值差异。具体而言,连接两颗星星 i,j,消耗的法力为 |b_i-b_j|
  • 用法力相连的两颗星星,孤独值更大的星星,其寿命不可以小于另一颗星星。具体而言,如果有两颗星星 i,j ,满足 b_i>b_ja_i< a_j ,那么这两颗星星就不可以用法力直接连接。

最初,每颗星星之间都是不相连的。为了使每颗星星都联通,归零者创造了一颗归零星,归零星寿命为 0 ,孤独值为 0 。这意味着任意一颗星星 i 都可以和归零星相连,并消耗法力 b_i

归零者想使这 n 颗星星和归零星联通,请你求出消耗的法力最少是多少。如果 ij 联通,jk 联通,那么 ik 也视为联通的,即便 ik 没有用法力直接连接。

输入

第一行输入一个整数 n(1\leq n \leq 2\times10^5) ,表示星星的数量。

第二行输入 n 个整数,第 i 个代表 a_i (1 \le a_i \le 2 \times 10^5)。

第三行输入 n 个整数,第 i 个代表 b_i (1 \le b_i \le 2 \times 10^5,且数据保证 b_i 互不相同)。

输出

输出一个整数,代表你的答案。

样例

标准输入 复制文本
3
9 8 7
1 2 3
标准输出 复制文本
6
标准输入 复制文本
5
2 6 5 3 5
1 2 3 5 4
标准输出 复制文本
9

来源

2023 天梯赛选拔赛 (重现)

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