Problem C: Barcelona FC Manager [Middle l]

Problem C: Barcelona FC Manager [Middle l]

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 1079  Solved: 221
[Submit][Status][Web Board]

Description

Karl is a fan of Barcelona FC(Football Club), but recently he is dissatisfied with the manager. So, he make a daydream to become a Barcelona FC manager and buy some football players. The Barcelona FC has infinite money, that means Karl can buy anyone he want. There are n players. For each player, it has a power \(a_i\). For Each hour, he can only buy one player. However, for the ith player, he can only be bought before \(b_i\)th hour(including the \(b_i\)th hour). Karl is short with algorithm, please help him to buy some players, which can make the sum of power as max.

Input

The first line contains an integer \(T(1\leq T\leq 10)\), indicating the number of test cases.

For each test cases, the first line contains an integer \(n(1\leq n\leq 10^5)\). The second line contains n integers \(a_1, a_2, a_3, ..., a_n(1\leq a_i\leq 10^5)\), indicating the power of each player. The third line contains n integers \(b_1, b_2, b_3, ..., b_n(1\leq b_i\leq 10^4)\), and \(b_i\) indicating Karl can only buy the player before \(b_i\)th hour(including the \(b_i\)th hour).

Output

For each test case, please print the max sum of power in one line.

Sample Input

3
3
2 1 3
1 1 2
4
50 10 20 30
2 1 2 1
7
20 2 10 100 8 5 50
1 1 3 2 2 20 10

Sample Output

5
80
185

HINT


For the test case, Karl can buy the first player and the third player to get the maximum sum of power 5.

[Submit][Status]