33OJ
登录 注册

#P17552. [JAG 2026 Summer Camp #2] Empty Intersection

[JAG 2026 Summer Camp #2] Empty Intersection

Problem Description

You are given two integer sequences A=(A1,…,AN)A=(A_1,\ldots,A_N) and B=(B1,…,BN)B=(B_1,\ldots,B_N), and two sequences of positive integers V=(V1,…,VN)V=(V_1,\ldots,V_N) and W=(W1,…,WN)W=(W_1,\ldots,W_N). All four sequences have length NN.

Choose two (possibly empty) intervals of indices, [L,R)[L,R) for AA and [U,D)[U,D) for BB. Here, L,R,U,DL,R,U,D are integers satisfying 1≤L≤R≤N+11\le L\le R\le N+1 and 1≤U≤D≤N+11\le U\le D\le N+1.

Let XX and YY be the sets of values occurring in these intervals, respectively:

X={Ai∣L≤i<R},X=\{A_i\mid L\le i<R\}, Y={Bj∣U≤j<D}.Y=\{B_j\mid U\le j<D\}.

The chosen intervals must satisfy X∩Y=∅X\cap Y=\varnothing. In other words, no value may occur in both intervals.

If L=RL=R, the interval of AA is empty and X=∅X=\varnothing. Likewise, if U=DU=D, the interval of BB is empty and Y=∅Y=\varnothing.

The score of the two chosen intervals is

∑i=LR−1Vi+∑j=UD−1Wj.\sum_{i=L}^{R-1}V_i+\sum_{j=U}^{D-1}W_j.

Find the maximum possible score among all valid choices.

Input Format

The input contains one or more test cases. The first line of the input contains an integer TT (1≤T≤1041\le T\le 10^4), which is the number of test cases. The descriptions of the TT test cases follow, each in the format below.

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
V_1 V_2 ... V_N
W_1 W_2 ... W_N

The first line contains a single integer NN, the common length of the four sequences (1≤N≤2×1051\le N\le 2\times 10^5).

The following four lines contain NN integers each and describe the sequences AA, BB, VV, and WW, respectively.

The integers AiA_i and BiB_i satisfy 1≤Ai,Bi≤N1\le A_i,B_i\le N for every ii (1≤i≤N1\le i\le N).

The integers ViV_i and WiW_i satisfy 1≤Vi,Wi≤1091\le V_i,W_i\le 10^9 for every ii (1≤i≤N1\le i\le N).

The sum of NN over all test cases does not exceed 6×1056\times 10^5.

Output Format

Output TT lines. The ii-th line should contain the maximum possible score for the ii-th test case.

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
13
15
33
11

Hint

In the first test case, we can choose the interval [1,3)[1,3) of AA and the interval [1,2)[1,2) of BB. More precisely, we can set L=1L=1, R=3R=3, U=1U=1, and D=2D=2. Their sets of values are {1,2}\{1,2\} and {3}\{3\}, respectively, and they are disjoint. The score is

V1+V2+W1=3+4+6=13,V_1+V_2+W_1=3+4+6=13,

which is the maximum possible score.

In the second test case, we can choose an empty interval of AA and the entire interval [1,4)[1,4) of BB. More precisely, L=2L=2, R=2R=2, U=1U=1, and D=4D=4.