Gegeben sind zwei Folgen ganzer Zahlen $A = (A_1, \dots, A_N)$ und $B = (B_1, \dots, B_N)$ sowie zwei Folgen positiver ganzer Zahlen $V = (V_1, \dots, V_N)$ und $W = (W_1, \dots, W_N)$. Alle vier Folgen haben die Länge $N$.

Wähle zwei (möglicherweise leere) Indexintervalle, $[L, R)$ für $A$ und $[U, D)$ für $B$. Dabei sind $L, R, U, D$ ganze Zahlen mit $1 \le L \le R \le N + 1$ und $1 \le U \le D \le N + 1$.

Seien $X$ und $Y$ jeweils die Mengen der Werte, die in diesen Intervallen vorkommen:

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

Die gewählten Intervalle müssen $X \cap Y = \emptyset$ erfüllen. Mit anderen Worten: Kein Wert darf in beiden Intervallen gleichzeitig vorkommen.

Falls $L = R$ gilt, ist das Intervall von $A$ leer und $X = \emptyset$. Ebenso ist im Fall $U = D$ das Intervall von $B$ leer und $Y = \emptyset$.

Die Punktzahl der beiden gewählten Intervalle beträgt

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

Bestimme die maximal mögliche Punktzahl unter allen gültigen Auswahlmöglichkeiten.

Eingabe

Die Eingabe besteht aus einem oder mehreren Testfällen. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgen die Beschreibungen der $T$ Testfälle, jeweils im unten angegebenen Format.

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

Die erste Zeile enthält eine einzelne ganze Zahl $N$, die gemeinsame Länge der vier Folgen ($1 \le N \le 2 \times 10^5$).

Die folgenden vier Zeilen enthalten jeweils $N$ ganze Zahlen und beschreiben der Reihe nach die Folgen $A$, $B$, $V$ und $W$.

Die ganzen Zahlen $A_i$ und $B_i$ erfüllen $1 \le A_i, B_i \le N$ für jedes $i$ ($1 \le i \le N$).

Die ganzen Zahlen $V_i$ und $W_i$ erfüllen $1 \le V_i, W_i \le 10^9$ für jedes $i$ ($1 \le i \le N$).

Die Summe von $N$ über alle Testfälle hinweg überschreitet nicht $6 \times 10^5$.

Ausgabe

Gib $T$ Zeilen aus. Die $i$-te Zeile soll die maximal mögliche Punktzahl für den $i$-ten Testfall enthalten.

Beispiele

Eingabe 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

Ausgabe 1

13
15
33
11

Hinweis

Im ersten Testfall können wir das Intervall $[1, 3)$ von $A$ und das Intervall $[1, 2)$ von $B$ wählen. Genauer gesagt können wir $L = 1$, $R = 3$, $U = 1$ und $D = 2$ setzen. Ihre Wertemengen sind $\{1, 2\}$ bzw. $\{3\}$, und sie sind disjunkt. Die Punktzahl ist

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

was die maximal mögliche Punktzahl ist.

Im zweiten Testfall können wir ein leeres Intervall von $A$ und das gesamte Intervall $[1, 4)$ von $B$ wählen. Genauer gesagt gilt $L = 2$, $R = 2$, $U = 1$ und $D = 4$.