กำหนดลำดับของจำนวนเต็มสองลำดับคือ $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$ สอดคล้องกับ $1 \le A_i, B_i \le N$ สำหรับทุกค่า $i$ ($1 \le i \le N$)

จำนวนเต็ม $V_i$ และ $W_i$ สอดคล้องกับ $1 \le V_i, W_i \le 10^9$ สำหรับทุกค่า $i$ ($1 \le i \le N$)

ผลรวมของ $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$