#P18378. Degree Sequence 3
Degree Sequence 3
Degree Sequence 3
题目描述
在第二届 Universal Cup 半决赛期间,你在奇琴伊察发现了一些古代玛雅人研究图论的记录,其中记载着一些树的度数序列。
后来,在 2024 年贵安 ICPC 集训营中,你或许已经做过 Degree Sequence 2。小青鱼很想向你介绍那道题,但是它可能会作为第四届 Universal Cup 的常规场次出现,因此他暂时不能透露。
不过,不必失望!谁说必须先做 Degree Sequence 2,才能挑战 Degree Sequence 3 呢?
回顾度数序列的定义:对于一张有 个顶点的简单无向图,记顶点 的度数为 ,即与该顶点关联的边数。那么整数序列 就称为这张图的度数序列。简单图不允许重边或自环。

如果存在一张简单无向图,其度数序列恰好为整数序列 ,则称 是一个合法度数序列。例如, 是合法度数序列,上图就是一种实现。
现在,小青鱼给你两个长度为 的整数序列 。他希望将 变为一个简单无向图的合法度数序列。为此,他可以执行任意多次以下操作:
- 选择一个下标 ,令 ,花费 元。
- 选择一个下标 ,令 ,同样花费 元。
请你求出所需的最小总费用。
目标图的顶点数仍为 ,不要求连通,也不要求是一棵树。只需输出最小费用,无须输出目标图或操作方案。
输入格式
输入包含多组测试数据。第一行包含整数 (),表示测试数据组数。
对于每组测试数据:
第一行包含整数 ()。
第二行包含 个整数 (),表示初始序列。注意,初始值可以等于 。
第三行包含 个整数 (),表示每次对相应位置增减 的费用。
保证所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,输出一行一个整数,表示将 变为合法度数序列的最小总费用。
样例输入
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
样例说明
第一组数据无需执行操作,因为 已经是合法度数序列。一种实现如下。

第二组数据,最优方案是令 ,得到 ,总费用为 。
第三组数据,最优方案是先令 ,再对 执行两次加 ,得到 ,总费用为 。目标序列的一种实现如下。
