Anda diberikan dua barisan bilangan bulat $A = (A_1, \dots, A_N)$ dan $B = (B_1, \dots, B_N)$, serta dua barisan bilangan bulat positif $V = (V_1, \dots, V_N)$ dan $W = (W_1, \dots, W_N)$. Keempat barisan tersebut memiliki panjang $N$.

Pilih dua interval indeks (boleh kosong), $[L, R)$ untuk $A$ dan $[U, D)$ untuk $B$. Di sini, $L, R, U, D$ adalah bilangan bulat yang memenuhi $1 \le L \le R \le N + 1$ dan $1 \le U \le D \le N + 1$.

Misalkan $X$ dan $Y$ masing-masing adalah himpunan nilai yang muncul pada interval-interval tersebut:

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

Interval yang dipilih harus memenuhi $X \cap Y = \emptyset$. Dengan kata lain, tidak ada nilai yang boleh muncul di kedua interval.

Jika $L = R$, interval dari $A$ kosong dan $X = \emptyset$. Demikian pula, jika $U = D$, interval dari $B$ kosong dan $Y = \emptyset$.

Skor dari kedua interval yang dipilih adalah

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

Carilah skor maksimum yang mungkin di antara semua pilihan yang valid.

Masukan

Masukan berisi satu atau lebih kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji. Deskripsi dari $T$ kasus uji menyusul, masing-masing dalam format di bawah ini.

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

Baris pertama berisi sebuah bilangan bulat $N$, panjang keempat barisan ($1 \le N \le 2 \times 10^5$).

Empat baris berikutnya masing-masing berisi $N$ bilangan bulat dan mendeskripsikan barisan $A$, $B$, $V$, dan $W$ secara berturut-turut.

Bilangan bulat $A_i$ dan $B_i$ memenuhi $1 \le A_i, B_i \le N$ untuk setiap $i$ ($1 \le i \le N$).

Bilangan bulat $V_i$ dan $W_i$ memenuhi $1 \le V_i, W_i \le 10^9$ untuk setiap $i$ ($1 \le i \le N$).

Jumlah $N$ di seluruh kasus uji tidak melebihi $6 \times 10^5$.

Keluaran

Keluarkan $T$ baris. Baris ke-$i$ harus berisi skor maksimum yang mungkin untuk kasus uji ke-$i$.

Contoh

Masukan 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

Keluaran 1

13
15
33
11

Catatan

Pada kasus uji pertama, kita dapat memilih interval $[1, 3)$ dari $A$ dan interval $[1, 2)$ dari $B$. Lebih tepatnya, kita dapat menetapkan $L = 1$, $R = 3$, $U = 1$, dan $D = 2$. Himpunan nilai keduanya masing-masing adalah $\{1, 2\}$ dan $\{3\}$, serta saling lepas. Skornya adalah

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

yang merupakan skor maksimum yang mungkin.

Pada kasus uji kedua, kita dapat memilih interval kosong dari $A$ dan seluruh interval $[1, 4)$ dari $B$. Lebih tepatnya, $L = 2$, $R = 2$, $U = 1$, dan $D = 4$.