"宇宙是一座黑暗森林,每个文明都是带枪的猎人。如果发现了别的生命,能做的只有一件事:开枪消灭..."
在黑暗森林的宇宙里,分布着 颗星星,每颗星星都有寿命 和自己专属的孤独值 。看着这些孤单的星星,归零者决定用法力把所有的星星连接在一起,但是归零者的魔法需要遵循下面的物理规律:
最初,每颗星星之间都是不相连的。为了使每颗星星都联通,归零者创造了一颗归零星,归零星寿命为 ,孤独值为 。这意味着任意一颗星星 都可以和归零星相连,并消耗法力 。
归零者想使这 颗星星和归零星联通,请你求出消耗的法力最少是多少。如果 和 联通, 和 联通,那么 和 也视为联通的,即便 和 没有用法力直接连接。
输入
第一行输入一个整数 ,表示星星的数量。
第二行输入 个整数,第 个代表 ()。
第三行输入 个整数,第 个代表 (,且数据保证 互不相同)。
输出
输出一个整数,代表你的答案。
样例
标准输入 复制文本 |
3 9 8 7 1 2 3 |
标准输出 复制文本 |
6 |
标准输入 复制文本 |
5 2 6 5 3 5 1 2 3 5 4 |
标准输出 复制文本 |
9 |
来源
2023 天梯赛选拔赛 (重现)