B. Skipping
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It is already the year $$$3024$$$, ideas for problems have long run out, and the olympiad now takes place in a modified individual format. The olympiad consists of $$$n$$$ problems, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th problem has its own score $$$a_i$$$ and a certain parameter $$$b_i$$$ ($$$1 \le b_i \le n$$$).

Initially, the testing system gives the participant the first problem. When the participant is given the $$$i$$$-th problem, they have two options:

  • They can submit the problem and receive $$$a_i$$$ points;
  • They can skip the problem, in which case they will never be able to submit it.

Then, the testing system selects the next problem for the participant from problems with indices $$$j$$$, such that:

  • If he submitted the $$$i$$$-th problem, it looks at problems with indices $$$j < i$$$;
  • If he skipped the $$$i$$$-th problem, it looks at problems with indices $$$j \leq b_i$$$.

Among these problems, it selects the problem with the maximum index that it has not previously given to the participant (he has neither submitted nor skipped it before). If there is no such problem, then the competition for the participant ends, and their result is equal to the sum of points for all submitted problems. In particular, if the participant submits the first problem, then the competition for them ends. Note that the participant receives each problem at most once.

Prokhor has prepared thoroughly for the olympiad, and now he can submit any problem. Help him determine the maximum number of points he can achieve.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^5$$$) — the number of problems in the olympiad.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the scores of the problems.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$) — the parameters of the problems.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum number of points that Prokhor can achieve.

Example
Input
4
2
15 16
2 1
5
10 10 100 100 1000
3 4 1 1 1
3
100 49 50
3 2 2
4
100 200 300 1000
2 3 4 1
Output
16
200
100
1000
Note

In the first test case, Prokhor can skip the first problem; then he will receive the problem with index $$$b_1 = 2$$$. Prokhor can submit it and receive $$$a_2 = 16$$$ points. After that, the competition will end because Prokhor has already received all problems. Note that if Prokhor submits the first problem, he will receive $$$a_1 = 15$$$ points, but the competition will end immediately.

In the second test case, Prokhor can skip the first problem; then he will receive the problem with index $$$b_1 = 3$$$. Prokhor can submit it and receive $$$a_3 = 100$$$ points. After that, Prokhor will receive the second problem, which he can skip to receive the problem with index $$$b_2 = 4$$$. Prokhor can submit the fourth problem and receive another $$$a_4 = 100$$$ points. After that, the competition ends because Prokhor has already received all problems with indices not exceeding $$$4$$$. Thus, Prokhor will receive a total of $$$200$$$ points.

In the third test case, Prokhor can submit the first problem and receive $$$100$$$ points, after which the competition will end immediately.