Du får gitt to heltallsfølger $A = (A_1, \dots, A_N)$ og $B = (B_1, \dots, B_N)$, samt to følger av positive heltall $V = (V_1, \dots, V_N)$ og $W = (W_1, \dots, W_N)$. Alle de fire følgene har lengde $N$.

Velg to (muligens tomme) intervaller av indekser, $[L, R)$ for $A$ og $[U, D)$ for $B$. Her er $L, R, U, D$ heltall som oppfyller $1 \le L \le R \le N + 1$ og $1 \le U \le D \le N + 1$.

La $X$ og $Y$ være mengdene av verdier som forekommer i henholdsvis disse intervallene:

$$ \begin{aligned} X &= \{A_i \mid L \le i < R\}, \\ Y &= \{B_j \mid U \le j < D\}. \end{aligned} $$

De valgte intervallene må oppfylle $X \cap Y = \emptyset$. Med andre ord kan ingen verdi forekomme i begge intervallene.

Hvis $L = R$, er intervallet til $A$ tomt og $X = \emptyset$. Tilsvarende, hvis $U = D$, er intervallet til $B$ tomt og $Y = \emptyset$.

Poengsummen for de to valgte intervallene er

$$ \sum_{i=L}^{R-1} V_i + \sum_{j=U}^{D-1} W_j. $$

Finn den maksimalt mulige poengsummen blant alle gyldige valg.

Inndata

Inndataene inneholder ett eller flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$), som er antall testtilfeller. Beskrivelsene av de $T$ testtilfellene følger, hver i formatet nedenfor.

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \\ &V_1 \ V_2 \ \dots \ V_N \\ &W_1 \ W_2 \ \dots \ W_N \end{aligned} $$

Den første linjen inneholder et enkelt heltall $N$, den felles lengden på de fire følgene ($1 \le N \le 2 \times 10^5$).

De neste fire linjene inneholder $N$ heltall hver og beskriver henholdsvis følgene $A$, $B$, $V$ og $W$.

Heltallene $A_i$ og $B_i$ oppfyller $1 \le A_i, B_i \le N$ for hver $i$ ($1 \le i \le N$).

Heltallene $V_i$ og $W_i$ oppfyller $1 \le V_i, W_i \le 10^9$ for hver $i$ ($1 \le i \le N$).

Summen av $N$ over alle testtilfeller overstiger ikke $6 \times 10^5$.

Utdata

Skriv ut $T$ linjer. Den $i$-te linjen skal inneholde den maksimalt mulige poengsummen for det $i$-te testtilfellet.

Eksempler

Inndata 1

4
3
1 2 3
3 2 1
3 4 5
6 2 1
3
1 1 1
1 1 1
2 3 4
5 5 5
4
1 2 1 3
4 2 4 3
5 6 5 1
4 10 4 10
5
3 1 2 4 3
1 1 2 2 4
1 3 3 2 1
2 2 3 1 1

Utdata 1

13
15
33
11

Merk

I det første testtilfellet kan vi velge intervallet $[1, 3)$ av $A$ og intervallet $[1, 2)$ av $B$. Mer presist kan vi sette $L = 1$, $R = 3$, $U = 1$ og $D = 2$. Verdimengdene deres er henholdsvis $\{1, 2\}$ og $\{3\}$, og de er disjunkte. Poengsummen er

$$ V_1 + V_2 + W_1 = 3 + 4 + 6 = 13, $$

som er den maksimalt mulige poengsummen.

I det andre testtilfellet kan vi velge et tomt intervall av $A$ og hele intervallet $[1, 4)$ av $B$. Mer presist: $L = 2$, $R = 2$, $U = 1$ og $D = 4$.