Annettuna on kaksi kokonaislukujonoa $A = (A_1, \dots, A_N)$ ja $B = (B_1, \dots, B_N)$ sekä kaksi positiivisten kokonaislukujen jonoa $V = (V_1, \dots, V_N)$ ja $W = (W_1, \dots, W_N)$. Kaikkien neljän jonon pituus on $N$.

Valitse kaksi (mahdollisesti tyhjää) indeksiväliä, $[L, R)$ jonolle $A$ ja $[U, D)$ jonolle $B$. Tässä $L, R, U, D$ ovat kokonaislukuja, jotka toteuttavat ehdot $1 \le L \le R \le N + 1$ ja $1 \le U \le D \le N + 1$.

Olkoot $X$ ja $Y$ näillä väleillä esiintyvien arvojen joukot vastaavasti:

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

Valittujen välien on toteutettava ehto $X \cap Y = \emptyset$. Toisin sanoen mikään arvo ei saa esiintyä molemmilla väleillä.

Jos $L = R$, jonon $A$ väli on tyhjä ja $X = \emptyset$. Vastaavasti, jos $U = D$, jonon $B$ väli on tyhjä ja $Y = \emptyset$.

Kahden valitun välin pistemäärä on

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

Etsi suurin mahdollinen pistemäärä kaikkien kelvollisten valintojen joukosta.

Syöte

Syöte sisältää yhden tai useamman testitapauksen. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka on testitapausten lukumäärä. Seuraavaksi on $T$ testitapauksen kuvaukset, jokainen alla olevassa muodossa.

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

Ensimmäinen rivi sisältää yhden kokonaisluvun $N$, neljän jonon yhteisen pituuden ($1 \le N \le 2 \times 10^5$).

Seuraavat neljä riviä sisältävät kukin $N$ kokonaislukua ja kuvaavat jonot $A$, $B$, $V$ ja $W$ tässä järjestyksessä.

Kokonaisluvut $A_i$ ja $B_i$ toteuttavat ehdon $1 \le A_i, B_i \le N$ kaikilla $i$ ($1 \le i \le N$).

Kokonaisluvut $V_i$ ja $W_i$ toteuttavat ehdon $1 \le V_i, W_i \le 10^9$ kaikilla $i$ ($1 \le i \le N$).

Lukujen $N$ summa yli kaikkien testitapausten ei ylitä arvoa $6 \times 10^5$.

Tuloste

Tulosta $T$ riviä. $i$. rivin tulee sisältää suurin mahdollinen pistemäärä $i$. testitapaukselle.

Esimerkit

Syöte 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

Tuloste 1

13
15
33
11

Huomautus

Ensimmäisessä testitapauksessa voimme valita välin $[1, 3)$ jonosta $A$ ja välin $[1, 2)$ jonosta $B$. Tarkemmin sanoen voimme asettaa $L = 1$, $R = 3$, $U = 1$ ja $D = 2$. Niiden arvojoukot ovat $\{1, 2\}$ ja $\{3\}$ vastaavasti, ja ne ovat erilliset. Pistemäärä on

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

mikä on suurin mahdollinen pistemäärä.

Toisessa testitapauksessa voimme valita tyhjän välin jonosta $A$ ja koko välin $[1, 4)$ jonosta $B$. Tarkemmin sanoen $L = 2$, $R = 2$, $U = 1$ ja $D = 4$.