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$$$。
输出
对于每个测试用例,输出一个整数 - 消除所有测试用例所需的最小可能总成本 掉落.
示例
输入复制
10110541 2 2 35 6 7 844 3 2 11 1 1 133 1 2100 1 155 5 5 5 510 1 10 1 1051 3 2 2 4100 1 1 1 100610 9 8 7 6 51 100 1 100 1 1005100 1 100 100 1001 100 1 1 142 1 2 15 4 3 271 5 3 4 2 6 710 1 10 1 10 1 10
输出复制
0032012031611
注意
在第一个和第二个示例中,数组已经没有 掉落,因此不需要进行任何更改。
在第三个示例中,最佳数组之一是:$$$[2,3,5,6]$$$;为了实现这一点,除了第二个元素之外的所有元素都需要被替换,所以答案是$$$c_1 + c_3 + c_4 = 3$$$。