题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n$，以及每个位置的修改代价 $c_1,c_2,\dots,c_n$。

你可以选择任意一些位置进行修改。修改第 $i$ 个位置需要花费 $c_i$，并且可以把 $a_i$ 替换成任意整数。

修改完成后，如果存在某个 $i$ 满足：

1 <= i < n 且 a_i > a_{i+1}

则称位置 $i$ 是一个下降点。

请计算最小修改总代价，使得最终数组没有任何下降点，也就是最终数组非递减。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据包含三行：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个整数 $c_1,c_2,\dots,c_n$。

保证所有测试数据的 $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

样例说明

第一、二组测试数据中，原数组已经没有下降点，所以不需要修改，答案为 $0$。

第三组测试数据中，一种最优的最终数组可以是 $[2,3,5,6]$。为了得到它，除第二个位置外，其余位置都需要修改，因此总代价为 $c_1+c_3+c_4=3$。

数据范围

• $1 \le t \le 5000$
• $1 \le n \le 8000$
• $1 \le a_i \le 10^9$
• $1 \le c_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $8000$

来源

Codeforces Round 1062 (Div. 4), Problem G - Mukhammadali and the Smooth Array