On vous donne deux suites d'entiers $A = (A_1, \dots, A_N)$ et $B = (B_1, \dots, B_N)$, ainsi que deux suites d'entiers strictement positifs $V = (V_1, \dots, V_N)$ et $W = (W_1, \dots, W_N)$. Les quatre suites ont toutes pour longueur $N$.

Choisissez deux intervalles d'indices (éventuellement vides), $[L, R)$ pour $A$ et $[U, D)$ pour $B$. Ici, $L, R, U, D$ sont des entiers vérifiant $1 \le L \le R \le N + 1$ et $1 \le U \le D \le N + 1$.

Soient $X$ et $Y$ les ensembles des valeurs apparaissant respectivement dans ces intervalles :

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

Les intervalles choisis doivent vérifier $X \cap Y = \emptyset$. Autrement dit, aucune valeur ne peut apparaître dans les deux intervalles à la fois.

Si $L = R$, l'intervalle de $A$ est vide et $X = \emptyset$. De même, si $U = D$, l'intervalle de $B$ est vide et $Y = \emptyset$.

Le score des deux intervalles choisis est

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

Trouvez le score maximal possible parmi tous les choix valides.

Entrée

L'entrée contient un ou plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$), qui est le nombre de cas de test. Les descriptions des $T$ cas de test suivent, chacune dans le format ci-dessous.

$$ \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 première ligne contient un seul entier $N$, la longueur commune des quatre suites ($1 \le N \le 2 \times 10^5$).

Les quatre lignes suivantes contiennent chacune $N$ entiers et décrivent respectivement les suites $A$, $B$, $V$ et $W$.

Les entiers $A_i$ et $B_i$ vérifient $1 \le A_i, B_i \le N$ pour tout $i$ ($1 \le i \le N$).

Les entiers $V_i$ et $W_i$ vérifient $1 \le V_i, W_i \le 10^9$ pour tout $i$ ($1 \le i \le N$).

La somme de $N$ sur l'ensemble des cas de test ne dépasse pas $6 \times 10^5$.

Sortie

Affichez $T$ lignes. La $i$-ième ligne doit contenir le score maximal possible pour le $i$-ième cas de test.

Exemples

Entrée 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

Sortie 1

13
15
33
11

Remarque

Dans le premier cas de test, nous pouvons choisir l'intervalle $[1, 3)$ de $A$ et l'intervalle $[1, 2)$ de $B$. Plus précisément, nous pouvons poser $L = 1$, $R = 3$, $U = 1$ et $D = 2$. Leurs ensembles de valeurs sont respectivement $\{1, 2\}$ et $\{3\}$, et ils sont disjoints. Le score est

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

ce qui est le score maximal possible.

Dans le deuxième cas de test, nous pouvons choisir un intervalle vide de $A$ et l'intervalle entier $[1, 4)$ de $B$. Plus précisément, $L = 2$, $R = 2$, $U = 1$ et $D = 4$.