该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

某公司有 n 个连锁店，每个连锁店的当前月销售额为 $a_1, a_2, \ldots, a_n$。公司管理层可以调整任意连锁店的销售额数据，调整第 i 个连锁店需要成本 $c_i$，调整后可以将该店的销售额改为任意整数。未调整的连锁店必须保持其原始销售额数据。

调整完成后，如果第 i 个连锁店的最终销售额严格大于第 i+1 个连锁店的最终销售额，则称位置 i（$1 \leq i < n$）存在一个业绩下滑。管理层希望最终的销售额数据中不包含任何业绩下滑。

求确保销售额数据中不存在业绩下滑所需的最小调整成本。

Format

Input

第一行包含一个整数 $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$ ）。( $1 \le c_i \le 10^9$ ) - 变动成本。

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

Output

对于每个测试用例，输出一个整数 - 消除所有下降所需的最小可能总成本。

Samples

9
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
3
2
0
1
203
1
6
11

Limitation

1s, 1024KiB for each test case.