Elves and Dwarves are on war. Elves planted bombs on some of the Dwarves’ villages (Atmost one bomb in one village). But the bombs are not placed very strategically and can cancel each other’s effect. You are the leader of Elves’ army and have to decide which bomb to detonate in order to maximize the damage.

Each bomb has an associated range and damage. If A[1], A[2] ….. A[n] are Dwarves’ villages. Then detonating bomb placed at Ai with range R and Damage D causes damage D in village A[i], D-1 in village A[i+1], D-2 in village A[i+2] ….. 2 in village A[i+R-2] and 1 in village A[i+R-1].

There is one more phenomenon observed when detonating a bomb. Each bomb is of a particular type. If a bomb of type T placed at village A[i] is detonated, then all the bombs of type other than T in its range will be defused. Any bomb of type T in the range of bomb at A[i] if detonated will block the damage due to bomb at A[i] to propagate.

e.g. Bomb placed at 1(Damage 10,Range 6) and Bomb placed at 3(Damage 15,Range 2) are detonated, then for 6 villages

Damage at village 1 -> 10 (Due to bomb at 1)
Damage at village 2 -> 9 (Due to bomb at 1)
Damage at village 3 -> 15(Due to bomb at 3)
Damage at village 4 -> 14(Due to bomb at 3)
Damage at village 5 -> 0
Damage at village 6 -> 0

If only bomb at 1 is detonated and bomb at 3 is not detonated then
Damage at village 1 -> 10 (Due to bomb at 1)
Damage at village 2 -> 9 (Due to bomb at 1)
Damage at village 3 -> 8(Due to bomb at 1)
Damage at village 4 -> 7(Due to bomb at 1)
Damage at village 5 -> 6(Due to bomb at 1)
Damage at village 6 -> 5(Due to bomb at 1)

NOTE : All the bombs should be detonated at once (Not sequentially). Determine the total damage possible.

Input :
First line contains tc, the number of test cases.

First line of each test case contains n, the number of villages.
Next line contains n integers D[1],D[2]…D[n], D[i] denotes the damage value of bomb placed at village i. If there is no bomb at village i , D[i] equals 0.

Next line contains n integers T[1],T[2]…T[n], T[i] denotes the type of bomb placed at village i. If there is no bomb at village i , T[i] equals -1.

Next line contains n integers R[1],R[2]…R[n], R[i] denotes the range of bomb placed at village i. If there is no bomb at village i , R[i] equals 0.

Output:
For each test case, print a single integer, the maximum total damage value possible.

Constraints:
1 <=tc <= 10
1 <= n <= 100000
1<= D[i] <= 1000
1<= R[i] <= 10
1 <= T[i]<= n (T[i]=-1 in case of no bomb)