← 返回题目列表

Codeforces · 2167/G

G. Mukhammadali 和平滑阵列

中文机器翻译题面 查看原题

Muhammadali 有一个整数数组 $$$a_1,\dots,a_n$$$。他可以改变(替换)任何职位子集;改变位置 $$$i$$$ 花费 $$$c_i$$$ 并用他选择的任何整数替换 $$$a_i$$$ 。他不改变的立场必须保持原来的价值。

在所有更改之后,我们将索引 $$$i$$$ ($$$1 \le i \lt n$$$) 称为 掉落 如果位置 $$$i$$$ 处的最终值严格大于位置 $$$i+1$$$ 处的最终值。 Muhammadali 希望最终的数组不包含 掉落.

找出所需的最小变更成本,以确保没有 数组中的 掉落 。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例由三行组成:

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 8000$$$) — 数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — 更改的成本。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$8000$$$。

输出

对于每个测试用例,输出一个整数 - 消除所有测试用例所需的最小可能总成本 掉落.

示例

输入
复制

10
1
10
5
4
1 2 2 3
5 6 7 8
4
4 3 2 1
1 1 1 1
3
3 1 2
100 1 1
5
5 5 5 5 5
10 1 10 1 10
5
1 3 2 2 4
100 1 1 1 100
6
10 9 8 7 6 5
1 100 1 100 1 100
5
100 1 100 100 100
1 100 1 1 1
4
2 1 2 1
5 4 3 2
7
1 5 3 4 2 6 7
10 1 10 1 10 1 10

输出
复制

0
0
3
2
0
1
203
1
6
11

注意

在第一个和第二个示例中,数组已经没有 掉落,因此不需要进行任何更改。

在第三个示例中,最佳数组之一是:$$$[2,3,5,6]$$$;为了实现这一点,除了第二个元素之外的所有元素都需要被替换,所以答案是$$$c_1 + c_3 + c_4 = 3$$$。