E. Sheesh El Beesh
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a line of $$$n$$$ dominoes, numbered $$$1$$$ to $$$n$$$ from left to right. Each domino $$$i$$$ has a height $$$h_i$$$ and an associated cost $$$c_i$$$ to manually push it.

Your goal is to make all $$$n$$$ dominoes fall.

The rules for falling are as follows:

  • If you choose to manually push domino $$$i$$$, you incur a cost of $$$c_i$$$, and domino $$$i$$$ falls.
  • When a domino $$$j$$$ falls, it may cause a chain reaction. If domino $$$j$$$ has fallen and $$$j \lt n$$$, it will hit domino $$$j+1$$$. If $$$h_j \gt h_{j+1}$$$, then domino $$$j+1$$$ will also fall.
  • This chain reaction continues. If $$$j+1$$$ falls, it may cause $$$j+2$$$ to fall, and so on.
Formally, if you manually push domino $$$i$$$, it falls. Then, for any $$$j \ge i$$$, if domino $$$j$$$ has fallen and $$$j \lt n$$$ and $$$h_j \gt h_{j+1}$$$, then domino $$$j+1$$$ will also fall.

You can choose to manually push any set of dominoes. The total cost is the sum of the costs of all dominoes you manually push. Find the minimum total cost required to make all $$$n$$$ dominoes fall.

Input

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases. The description of each test case follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 200,000$$$), the number of dominoes.

The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 10^9$$$), the heights of the dominoes.

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

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer on a new line: the minimum total cost to make all $$$n$$$ dominoes fall.

Example
Input
3
5
3 1 4 1 5
2 1 3 4 1
10
10 9 8 7 6 5 4 3 2 1
2 3 1 4 5 1 2 3 4 5
4
1 2 3 4
1 2 3 4
Output
6
2
10