Du får två heltalsföljder $A = (A_1, \dots, A_N)$ och $B = (B_1, \dots, B_N)$, samt två följder av positiva heltal $V = (V_1, \dots, V_N)$ och $W = (W_1, \dots, W_N)$. Alla fyra följder har längden $N$.

Välj två (eventuellt tomma) indexintervall, $[L, R)$ för $A$ och $[U, D)$ för $B$. Här är $L, R, U, D$ heltal som uppfyller $1 \le L \le R \le N + 1$ och $1 \le U \le D \le N + 1$.

Låt $X$ och $Y$ vara mängderna av värden som förekommer i respektive intervall:

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

De valda intervallen måste uppfylla $X \cap Y = \emptyset$. Med andra ord får inget värde förekomma i båda intervallen.

Om $L = R$ är intervallet för $A$ tomt och $X = \emptyset$. På samma sätt, om $U = D$ är intervallet för $B$ tomt och $Y = \emptyset$.

Poängen för de två valda intervallen är

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

Hitta den maximalt möjliga poängen bland alla giltiga val.

Indata

Indata innehåller ett eller flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 10^4$), vilket är antalet testfall. Beskrivningarna av de $T$ testfallen följer, vart och ett i formatet nedan.

$$ \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örsta raden innehåller ett enda heltal $N$, den gemensamma längden på de fyra följderna ($1 \le N \le 2 \times 10^5$).

De följande fyra raderna innehåller $N$ heltal vardera och beskriver följderna $A$, $B$, $V$ respektive $W$.

Heltalen $A_i$ och $B_i$ uppfyller $1 \le A_i, B_i \le N$ för varje $i$ ($1 \le i \le N$).

Heltalen $V_i$ och $W_i$ uppfyller $1 \le V_i, W_i \le 10^9$ för varje $i$ ($1 \le i \le N$).

Summan av $N$ över alla testfall överstiger inte $6 \times 10^5$.

Utdata

Skriv ut $T$ rader. Den $i$-te raden ska innehålla den maximalt möjliga poängen för det $i$-te testfallet.

Exempel

Indata 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

Förklaring

I det första testfallet kan vi välja intervallet $[1, 3)$ av $A$ och intervallet $[1, 2)$ av $B$. Mer precist kan vi sätta $L = 1$, $R = 3$, $U = 1$ och $D = 2$. Deras värdemängder är $\{1, 2\}$ respektive $\{3\}$, och de är disjunkta. Poängen är

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

vilket är den maximalt möjliga poängen.

I det andra testfallet kan vi välja ett tomt intervall av $A$ och hela intervallet $[1, 4)$ av $B$. Mer precist: $L = 2$, $R = 2$, $U = 1$ och $D = 4$.