Se te dan dos secuencias de enteros $A = (A_1, \dots, A_N)$ y $B = (B_1, \dots, B_N)$, y dos secuencias de enteros positivos $V = (V_1, \dots, V_N)$ y $W = (W_1, \dots, W_N)$. Las cuatro secuencias tienen longitud $N$.

Elige dos intervalos de índices (posiblemente vacíos), $[L, R)$ para $A$ y $[U, D)$ para $B$. Aquí, $L, R, U, D$ son enteros que satisfacen $1 \le L \le R \le N + 1$ y $1 \le U \le D \le N + 1$.

Sean $X$ e $Y$ los conjuntos de valores que aparecen en estos intervalos, respectivamente:

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

Los intervalos elegidos deben satisfacer $X \cap Y = \emptyset$. En otras palabras, ningún valor puede aparecer en ambos intervalos.

Si $L = R$, el intervalo de $A$ es vacío y $X = \emptyset$. Del mismo modo, si $U = D$, el intervalo de $B$ es vacío e $Y = \emptyset$.

La puntuación de los dos intervalos elegidos es

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

Encuentra la máxima puntuación posible entre todas las elecciones válidas.

Entrada

La entrada contiene uno o más casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^4$), que es el número de casos de prueba. A continuación siguen las descripciones de los $T$ casos de prueba, cada una con el formato siguiente.

$$ \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 primera línea contiene un único entero $N$, la longitud común de las cuatro secuencias ($1 \le N \le 2 \times 10^5$).

Las cuatro líneas siguientes contienen $N$ enteros cada una y describen las secuencias $A$, $B$, $V$ y $W$, respectivamente.

Los enteros $A_i$ y $B_i$ satisfacen $1 \le A_i, B_i \le N$ para todo $i$ ($1 \le i \le N$).

Los enteros $V_i$ y $W_i$ satisfacen $1 \le V_i, W_i \le 10^9$ para todo $i$ ($1 \le i \le N$).

La suma de $N$ en todos los casos de prueba no supera $6 \times 10^5$.

Salida

Imprime $T$ líneas. La $i$-ésima línea debe contener la máxima puntuación posible para el $i$-ésimo caso de prueba.

Ejemplos

Entrada 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

Salida 1

13
15
33
11

Nota

En el primer caso de prueba, podemos elegir el intervalo $[1, 3)$ de $A$ y el intervalo $[1, 2)$ de $B$. Más precisamente, podemos fijar $L = 1$, $R = 3$, $U = 1$ y $D = 2$. Sus conjuntos de valores son $\{1, 2\}$ y $\{3\}$, respectivamente, y son disjuntos. La puntuación es

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

que es la máxima puntuación posible.

En el segundo caso de prueba, podemos elegir un intervalo vacío de $A$ y el intervalo completo $[1, 4)$ de $B$. Más precisamente, $L = 2$, $R = 2$, $U = 1$ y $D = 4$.