Problem Description

The Luogu contribution system is online!

Now there are $n$ people who are going to participate in a Luogu monthly contest, and everyone’s rating is distinct. The $i$-th person’s rating is $r_i$, and their contribution value is $c_i$.

Suppose the $i$-th person’s rating rank among these $n$ people is $a_i$ (ranking by rating from high to low), and their rank in the monthly contest is $b_i$. No two people have the same rank. That is, both $a$ and $b$ are permutations of $1$ to $n$. After the contest ends, everyone will perform the following operation:

• If $a_i=b_i$, then the $i$-th person’s rating does not change, so the $i$-th person does nothing.
• If $a_i>b_i$, then the $i$-th person’s rating increases, so the $i$-th person will upvote the problem setter, causing the problem setter’s contribution value to increase by $c_i$ ($c_i$ may be negative, in which case the problem setter’s contribution value decreases).
• If $a_i<b_i$, then the $i$-th person’s rating decreases, so the $i$-th person will downvote the problem setter, causing the problem setter’s contribution value to decrease by $c_i$ ($c_i$ may be negative, in which case the problem setter’s contribution value increases).

As the only problem setter of this monthly contest, your initial contribution value is $0$. You want to know: among all possible permutations $b$ (obviously, the permutation $a$ has already been determined before the contest), what is the maximum possible contribution value you can have after the contest ends.

Input Format

Read input from standard input.

This problem has multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case, the first line contains a positive integer $n$, indicating the number of contestants.

The second line contains $n$ non-negative integers $r_1,r_2,\ldots,r_n$, indicating the contestants’ ratings. It is guaranteed that for any $1\le i< n$, $r_i>r_{i+1}$.

The third line contains $n$ integers $c_1,c_2,\ldots,c_n$, indicating the contestants’ contribution values.

Output Format

Output to standard output.

For each test case, output one line with one integer, representing the maximum contribution value.

3
5
3816 3738 3726 3621 3582
111 109 -50 -22 208
8
8 7 6 5 4 3 2 1
128 1 0 0 0 0 1 0
10
10 9 8 7 6 5 4 3 2 1
1 1 4 5 1 4 1 9 1 9

280
1
34

Hint

[Sample Explanation #1]

For the first test case, label the five people in input order as A, B, C, D, E. Then when the contest ranking order is ABECD, the contribution value is maximized, equal to $0+0-(-50)-(-22)+208=280$. It can be proven that this is the only ranking order that can make the contribution value reach the maximum.

For the second test case, label the eight people in input order as A, B, C, D, E, F, G, H. Then when the contest ranking order is ABCDEGFH, the contribution value can reach the maximum value $1$. Note that in this case, there are multiple ranking orders that achieve the maximum contribution value.

[Sample #2]

See contrib/contrib2.in and contrib/contrib2.ans in the contestant directory.

[Sample #3]

See contrib/contrib3.in and contrib/contrib3.ans in the contestant directory.

[Constraints]

For all data, it is guaranteed that: $1\le T\le 5$, $1\le n\le 2\times 10^5$, $0\le r_i\le 10^9$, $-10^9\le c_i\le 10^9$, and for any $1\le i<n$, $r_i>r_{i+1}$.

• Special Property A: For any $1\le i<n$, it is guaranteed that $c_i=c_{i+1}$.
• Special Property B: For any $1\le i<n$, it is guaranteed that $c_i\le c_{i+1}$.
• Special Property C: For any $1\le i\le n$, it is guaranteed that $c_i\ge 0$.

Translated by ChatGPT 5