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 ai

and a certain parameter bi

(1≤bi≤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 ai

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≤bi

.

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≤t≤105

) — 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≤n≤4⋅105

) — the number of problems in the olympiad.

The second line of each test case contains n

integers a1,a2,…,an

(1≤ai≤109

) — the scores of the problems.

The third line of each test case contains n

integers b1,b2,…,bn

(1≤bi≤n

) — the parameters of the problems.

It is guaranteed that the sum of n

over all test cases does not exceed 4⋅105

.

Output

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

Example

InputCopy

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

OutputCopy

16

200

100

1000

Note

In the first test case, Prokhor can skip the first problem; then he will receive the problem with index b1=2

. Prokhor can submit it and receive a2=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 a1=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 b1=3

. Prokhor can submit it and receive a3=100

points. After that, Prokhor will receive the second problem, which he can skip to receive the problem with index b2=4

. Prokhor can submit the fourth problem and receive another a4=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.

always write short code and random short variable that are similar, highly optimized, no explanation and comment unique code