CF2167G.Mukhammadali and the Smooth Array

Muhammadali has an integer array $a_1,\dots,a_n$. He can change (replace) any subset of positions; changing position $i$ costs $c_i$ and replaces $a_i$ with any integer of his choice. The positions that he does not change must retain their original values.

After all changes, we call an index $i$ ($1 \le i \lt n$) a drop if the final value at position $i$ is strictly greater than the final value at position $i+1$. Muhammadali wants the final array to contain no drops.

Find the minimum cost of changes required to ensure that there are no drops in the array.

穆罕默德阿里有一个整数数组 $a_1,\dots,a_n$。他可以修改（替换）任意一个位置子集；修改位置 $i$ 的代价为 $c_i$，且会将 $a_i$ 替换为他任选的一个整数。未被修改的位置必须保持其原始值。

在所有修改完成后，若最终数组中位置 $i$（$1 \le i \lt n$）处的值严格大于位置 $i+1$ 处的值，则称索引 $i$ 为一个下降点（drop）。穆罕默德阿里希望最终数组中不包含任何下降点。

求确保数组中无下降点所需的最小修改总代价。

The first line contains an integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Each test case consists of three lines:

The first line contains a single integer $n$ ($1 \le n \le 8000$) — the length of the arrays.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.

The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of changes.

It is guaranteed that the sum of $n$ across all test cases does not exceed $8000$.

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

For each test case, output a single integer — the minimum possible total cost required to eliminate all drops.

对于每个测试用例，输出一个整数——消除所有水滴所需的最小总成本。

In the first and second examples, the array already has no drops, so no changes are needed.

In the third example, one of the optimal arrays is: $[2,3,5,6]$; to achieve this, all elements except the second need to be replaced, so the answer is $c_1 + c_3 + c_4 = 3$.

在第一个和第二个例子中，数组已经没有“下降”，因此无需进行任何更改。

在第三个例子中，一个最优数组为：$[2,3,5,6]$；为得到该数组，除第二个元素外的所有元素均需被替换，因此答案为 $c_1 + c_3 + c_4 = 3$。