度数序列 3 - 문제

在第二届 Universal Cup 半决赛中，你在奇琴伊察（Chichén Itzá）发现了玛雅文明研究图论的一些记录。在遗迹中，你发现了一些由古代玛雅人记录的树的度数序列。

之后，在贵安举办的 2024 ICPC 冬令营中，你可能（也可能没有）解决了“Degree Sequence 2”这一题。小青鱼（Little Cyan Fish）很想和你分享那道题，但由于该比赛可能会作为第四届 Universal Cup 的正式单场出现，他目前还不能透露。

但不要失望！谁说在尝试“Degree Sequence 3”之前必须先解决“Degree Sequence 2”？它这不就来了！

回顾度数序列（degree sequence）的定义：对于一个含有 $n$ 个顶点的无向简单图（即无重边、无自环），其度数序列是一个长度为 $n$ 的整数序列，记为 $d_1, d_2, \dots, d_n$，其中 $d_i$ 等于顶点 $i$ 的度数（即与顶点 $i$ 关联的边数）。

如果存在一个简单无向图，其度数序列恰好为 $a$，则称序列 $a$ 是可图化的（graphic），或者是一个合法的度数序列。例如，$(3, 4, 2, 2, 1, 2)$ 是一个合法的度数序列，因为上图所示的图对应的度数序列正是它。

现在，小青鱼给你一个序列 $a_1, a_2, \dots, a_n$。小青鱼希望你将该序列转换为一个简单无向图的合法度数序列。为此，小青鱼可以进行以下操作任意次：

给定序列 $a$ 和 $b$，你的任务是求出将序列 $a$ 转换为合法度数序列所需的最小总代价。

每个输入文件中包含多个测试用例。输入的第一行包含一个整数 $T$ ($T \ge 1$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$)，表示初始序列。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$)，表示修改每个位置的代价。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行，包含一个整数，表示答案。

3
3
2 1 1
100 1000 10000
3
2 1 0
100 10 1
5
1 2 3 4 5
1 10 100 1000 10000

0
1
10002

对于第一个测试用例，我们不需要进行任何操作，因为 $(2, 1, 1)$ 已经是一个合法的度数序列。

对于第二个测试用例，最优方案是更新 $a_3 \leftarrow a_3 + 1$，使得序列 $a$ 变为 $(2, 1, 1)$。总代价为 $b_3 = 1$。

对于第三个测试用例，最优方案是更新 $a_5 \leftarrow a_5 - 1$，然后更新 $a_1 \leftarrow a_1 + 1$ 两次，使得序列 $a$ 变为 $(3, 2, 3, 4, 4)$。总代价为 $2 \cdot b_1 + b_5 = 10002$。

QOJ.ac