C. Weighted Minimums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ both of length $$$n$$$, the score of a range $$$[l, r]$$$ is defined as follows :

  • for each $$$i$$$ from $$$l$$$ to $$$r$$$ add $$$b_i$$$ to the score if $$$a_i = \min\limits_{l \le j \le i} a_j$$$ or $$$a_i = \min\limits_{i \le j \le r} a_j$$$ .

i.e the score of a range is the sum of $$$b_i$$$ over all $$$i$$$ such that $$$a_i$$$ is a prefix minimum or a suffix minimum in the range.

Find the maximum score of a range.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t (1 \le t \le 5 \cdot 10 ^ 4)$$$. The description of the test cases follows.

The first line of each test case contains the integer $$$n (1 \le n \le 2 \cdot 10 ^ 6)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n (1 \le a_i \le 10^9)$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n (1 \le b_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10 ^ 6$$$.

Output

For each test case, output one integer: the maximum score of a range.

Example
Input
2
3
1 2 1
3 5 3
5
1 2 3 1 2
7 8 2 4 9
Output
8
21