Ti vengono date due sequenze di interi $A = (A_1, \dots, A_N)$ e $B = (B_1, \dots, B_N)$, e due sequenze di interi positivi $V = (V_1, \dots, V_N)$ e $W = (W_1, \dots, W_N)$. Tutte e quattro le sequenze hanno lunghezza $N$.

Scegli due intervalli di indici (eventualmente vuoti), $[L, R)$ per $A$ e $[U, D)$ per $B$. Qui, $L, R, U, D$ sono interi che soddisfano $1 \le L \le R \le N + 1$ e $1 \le U \le D \le N + 1$.

Siano $X$ e $Y$ gli insiemi dei valori che compaiono rispettivamente in questi intervalli:

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

Gli intervalli scelti devono soddisfare $X \cap Y = \emptyset$. In altre parole, nessun valore può comparire in entrambi gli intervalli.

Se $L = R$, l'intervallo di $A$ è vuoto e $X = \emptyset$. Allo stesso modo, se $U = D$, l'intervallo di $B$ è vuoto e $Y = \emptyset$.

Il punteggio dei due intervalli scelti è

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

Trova il massimo punteggio possibile tra tutte le scelte valide.

Input

L'input contiene uno o più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$), che rappresenta il numero di casi di test. Seguono le descrizioni dei $T$ casi di test, ciascuna nel formato seguente.

$$ \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} $$

La prima riga contiene un singolo intero $N$, la lunghezza comune delle quattro sequenze ($1 \le N \le 2 \times 10^5$).

Le quattro righe seguenti contengono $N$ interi ciascuna e descrivono rispettivamente le sequenze $A$, $B$, $V$ e $W$.

Gli interi $A_i$ e $B_i$ soddisfano $1 \le A_i, B_i \le N$ per ogni $i$ ($1 \le i \le N$).

Gli interi $V_i$ e $W_i$ soddisfano $1 \le V_i, W_i \le 10^9$ per ogni $i$ ($1 \le i \le N$).

La somma di $N$ su tutti i casi di test non supera $6 \times 10^5$.

Output

Stampa $T$ righe. La $i$-esima riga deve contenere il punteggio massimo possibile per l'$i$-esimo caso di test.

Esempi

Input 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

Output 1

13
15
33
11

Note

Nel primo caso di test, possiamo scegliere l'intervallo $[1, 3)$ di $A$ e l'intervallo $[1, 2)$ di $B$. Più precisamente, possiamo porre $L = 1$, $R = 3$, $U = 1$ e $D = 2$. I rispettivi insiemi di valori sono $\{1, 2\}$ e $\{3\}$, e sono disgiunti. Il punteggio è

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

che è il punteggio massimo possibile.

Nel secondo caso di test, possiamo scegliere un intervallo vuoto di $A$ e l'intero intervallo $[1, 4)$ di $B$. Più precisamente, $L = 2$, $R = 2$, $U = 1$ e $D = 4$.