修改
题目描述
给定一个长度为 $n$ 的整数序列 $a_i$,再给定一个长度为 $n$ 的整数序列 $b_i$。
你可以进行一些修改,每次你可以将一个 $a_i$ 增加 $1$,花费为 $b_i$,你需要使所有的 $a_i$ 不相等,且同时满足花费最少。
但 zbw 认为太过简单,于是他规定,你可以在修改前进行**无限**次如下操作:交换 $b_i,b_j(1 \leq i,j \leq n)$。
求最小的花费。
**由于答案可能很大,请输出答案对 $2^{64}$ 取模后的值。**
输入输出格式
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数,第 $i$ 个数表示 $a_i$。
第三行 $n$ 个整数,第 $i$ 个数表示 $b_i$。
输出格式
输出一行一个整数,表示答案对 $2^{64}$ 取模的值。
输入输出样例
输入样例 #1
3
3 3 3
1 2 3
输出样例 #1
4
输入样例 #2
3
3 3 4
3 2 1
输出样例 #2
2
输入样例 #3
3
3 4 5
2 1 3
输出样例 #3
0
说明
样例 $1$:不改变 $b$,让 $a_1$ 增加 $2$,$a_2$ 增加 $1$,总花费为 $4$。
样例 $2$:交换 $b_1,b_3$,让 $a_1$ 增加 $2$,总花费为 $2$。
样例 $3$:不做任何改变。
**本题输入量较大,请使用读入优化。**
| 测试点 |$n$ |$a_i$ |特殊性质|
| :----------: | :----------: | :----------: | :----------: |
| $1,2$ |$\leq10$ |$\leq10^9$ |无 |
| $3\sim6$ |$\leq10^3$ |$\leq10^9$ |无|
| $7\sim10$ |$\leq10^6$ |$\leq10^6$ | 无|
| $11\sim14$ |$\leq10^6$ |$\leq10^9$ |所有 $b_i$ 相等 |
| $15\sim20$ |$\leq10^6$ |$\leq10^9$ |无|
对于所有数据 $1 \leq n \leq 10^6$,$1\leq a_i,b_i\leq10^9$。