题目描述

Humpy 有一个整数数组 $a_1,\dots,a_n$。他可以任意选择若干位置进行修改：修改位置 $i$ 的代价为 $c_i$，修改后可以把 $a_i$ 变为任意整数；未修改的位置必须保持原值。

在所有修改完成后，如果最终数组中存在下标 $i$（$1\le i<n$）使得最终第 $i$ 个位置上的值严格大于第 $i+1$ 个位置上的值，则称下标 $i$ 为一个 drop（下降）。Humpy 希望最终数组 没有任何 drop（即最终数组是非降的，$a_1\le a_2\le\cdots\le a_n$）。

请你计算达到该目标所需的最小总修改代价。

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一行，包含一个整数：使最终数组没有 drop 所需的最小总代价。

样例输入

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$。
• 第三组样例（$n=4$, $a=[4,3,2,1]$, $c=[1,1,1,1]$）：可以把数组修改为非降序，例如将除第二个元素外的元素都改为适当值，总代价为 $3$（修改三处，每处代价 $1$），这是最小可能代价之一。