P9742 "KDOI-06-J" Contribution System

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

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 to standard output. For each test case, output one line with one integer, representing the maximum contribution value.

**[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 ir_{i+1}$. | Test Point ID | $n\le $ | Special Constraints | | :-----------: | :------------: | :-----------------: | | $1\sim3$ | $8$ | None | | $4$ | $100$ | ABC | | $5$ | $100$ | C | | $6\sim 7$ | $100$ | None | | $8\sim 9$ | $5\times 10^3$ | AB | | $10\sim 11$ | $5\times 10^3$ | C | | $12\sim 14$ | $5\times 10^3$ | None | | $15$ | $2\times10^5$ | AB | | $16\sim 18$ | $2\times10^5$ | B | | $19\sim 21$ | $2\times10^5$ | C | | $22\sim 25$ | $2\times 10^5$ | None | + Special Property A: For any $1\le i