Bạn được cho hai dãy số nguyên $A = (A_1, \dots, A_N)$ và $B = (B_1, \dots, B_N)$, cùng hai dãy số nguyên dương $V = (V_1, \dots, V_N)$ và $W = (W_1, \dots, W_N)$. Cả bốn dãy đều có độ dài $N$.

Hãy chọn hai đoạn chỉ số (có thể rỗng), $[L, R)$ cho $A$ và $[U, D)$ cho $B$. Ở đây, $L, R, U, D$ là các số nguyên thỏa mãn $1 \le L \le R \le N + 1$ và $1 \le U \le D \le N + 1$.

Gọi $X$ và $Y$ lần lượt là tập hợp các giá trị xuất hiện trong các đoạn này:

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

Các đoạn được chọn phải thỏa mãn $X \cap Y = \emptyset$. Nói cách khác, không có giá trị nào được phép xuất hiện ở cả hai đoạn.

Nếu $L = R$, đoạn của $A$ là rỗng và $X = \emptyset$. Tương tự, nếu $U = D$, đoạn của $B$ là rỗng và $Y = \emptyset$.

Điểm số của hai đoạn được chọn là

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

Hãy tìm điểm số lớn nhất có thể trong tất cả các cách chọn hợp lệ.

Dữ liệu vào

Dữ liệu vào chứa một hoặc nhiều bộ test. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$), là số lượng bộ test. Mô tả của $T$ bộ test tiếp theo, mỗi bộ test có định dạng dưới đây.

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

Dòng đầu tiên chứa một số nguyên $N$, độ dài chung của bốn dãy ($1 \le N \le 2 \times 10^5$).

Bốn dòng tiếp theo, mỗi dòng chứa $N$ số nguyên và lần lượt mô tả các dãy $A$, $B$, $V$ và $W$.

Các số nguyên $A_i$ và $B_i$ thỏa mãn $1 \le A_i, B_i \le N$ với mọi $i$ ($1 \le i \le N$).

Các số nguyên $V_i$ và $W_i$ thỏa mãn $1 \le V_i, W_i \le 10^9$ với mọi $i$ ($1 \le i \le N$).

Tổng của $N$ trên tất cả các bộ test không vượt quá $6 \times 10^5$.

Dữ liệu ra

In ra $T$ dòng. Dòng thứ $i$ chứa điểm số lớn nhất có thể cho bộ test thứ $i$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

13
15
33
11

Ghi chú

Trong bộ test đầu tiên, ta có thể chọn đoạn $[1, 3)$ của $A$ và đoạn $[1, 2)$ của $B$. Chính xác hơn, ta có thể đặt $L = 1$, $R = 3$, $U = 1$ và $D = 2$. Tập hợp các giá trị của chúng lần lượt là $\{1, 2\}$ và $\{3\}$, và chúng rời nhau. Điểm số là

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

đây là điểm số lớn nhất có thể.

Trong bộ test thứ hai, ta có thể chọn một đoạn rỗng của $A$ và toàn bộ đoạn $[1, 4)$ của $B$. Chính xác hơn, $L = 2$, $R = 2$, $U = 1$ và $D = 4$.