Сізге екі бүтін сандар тізбегі $A = (A_1, \dots, A_N)$ мен $B = (B_1, \dots, B_N)$ және екі оң бүтін сандар тізбегі $V = (V_1, \dots, V_N)$ мен $W = (W_1, \dots, W_N)$ берілген. Төрт тізбектің де ұзындығы $N$-ге тең.

Индекстердің (бос болуы мүмкін) екі аралығын таңдаңыз: $[L, R)$ аралығы $A$ үшін және $[U, D)$ аралығы $B$ үшін. Мұндағы $L, R, U, D$ — $1 \le L \le R \le N + 1$ және $1 \le U \le D \le N + 1$ шарттарын қанағаттандыратын бүтін сандар.

$X$ және $Y$ сәйкесінше осы аралықтарда кездесетін мәндердің жиындары болсын:

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

Таңдалған аралықтар $X \cap Y = \emptyset$ шартын қанағаттандыруы тиіс. Басқаша айтқанда, ешбір мән екі аралықта бірдей кездеспеуі керек.

Егер $L = R$ болса, онда $A$ аралығы бос және $X = \emptyset$. Дәл сол сияқты, егер $U = D$ болса, онда $B$ аралығы бос және $Y = \emptyset$.

Таңдалған екі аралықтың ұпайы мынаған тең:

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

Барлық жарамды таңдаулардың ішінен мүмкін болатын ең үлкен ұпайды табыңыз.

Кіріс деректер

Кіріс деректер бір немесе бірнеше тест жағдайынан тұрады. Кірістің бірінші жолында тест жағдайларының санын білдіретін $T$ ($1 \le T \le 10^4$) бүтін саны берілген. Одан кейін төмендегі форматта $T$ тест жағдайының сипаттамалары беріледі.

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

Бірінші жолда төрт тізбектің ортақ ұзындығын білдіретін бір бүтін сан $N$ ($1 \le N \le 2 \times 10^5$) берілген.

Келесі төрт жолдың әрқайсысында $N$ бүтін саннан бар және олар сәйкесінше $A$, $B$, $V$ және $W$ тізбектерін сипаттайды.

$A_i$ және $B_i$ бүтін сандары әрбір $i$ ($1 \le i \le N$) үшін $1 \le A_i, B_i \le N$ шартын қанағаттандырады.

$V_i$ және $W_i$ бүтін сандары әрбір $i$ ($1 \le i \le N$) үшін $1 \le V_i, W_i \le 10^9$ шартын қанағаттандырады.

Барлық тест жағдайлары бойынша $N$ мәндерінің қосындысы $6 \times 10^5$ шамасынан аспайды.

Шығыс деректер

$T$ жол шығарыңыз. $i$-ші жолда $i$-ші тест жағдайы үшін мүмкін болатын ең үлкен ұпай болуы тиіс.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

13
15
33
11

Ескертпе

Бірінші тест жағдайында біз $[1, 3)$ ($A$ тізбегінің аралығы) және $[1, 2)$ ($B$ тізбегінің аралығы) аралықтарын таңдай аламыз. Нақтырақ айтқанда, $L = 1$, $R = 3$, $U = 1$ және $D = 2$ деп ала аламыз. Олардың мәндер жиындары сәйкесінше $\{1, 2\}$ және $\{3\}$, әрі олар қиылыспайды. Ұпайы:

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

бұл мүмкін болатын ең үлкен ұпай.

Екінші тест жағдайында біз $A$ тізбегінің бос аралығын және $[1, 4)$ ($B$ тізбегінің толық аралығын) таңдай аламыз. Нақтырақ айтқанда: $L = 2$, $R = 2$, $U = 1$ және $D = 4$.