"宇宙是一座黑暗森林,每个文明都是带枪的猎人。如果发现了别的生命,能做的只有一件事:开枪消灭..."
在黑暗森林的宇宙里,分布着 n 颗星星,每颗星星都有寿命 a 和自己专属的孤独值 b 。看着这些孤单的星星,归零者决定用法力把所有的星星连接在一起,但是归零者的魔法需要遵循下面的物理规律:
最初,每颗星星之间都是不相连的。为了使每颗星星都联通,归零者创造了一颗归零星,归零星寿命为 0 ,孤独值为 0 。这意味着任意一颗星星 i 都可以和归零星相连,并消耗法力 b_i 。
归零者想使这 n 颗星星和归零星联通,请你求出消耗的法力最少是多少。如果 i 和 j 联通,j 和 k 联通,那么 i 和 k 也视为联通的,即便 i 和 k 没有用法力直接连接。
输入
第一行输入一个整数 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 天梯赛选拔赛 (重现)