P17552 [JAG 2026 Summer Camp #2] Empty Intersection

You are given two integer sequences $A=(A_1,\ldots,A_N)$ and $B=(B_1,\ldots,B_N)$, and two sequences of positive integers $V=(V_1,\ldots,V_N)$ and $W=(W_1,\ldots,W_N)$. All four sequences have length $N$. Choose two (possibly empty) intervals of indices, $[L,R)$ for $A$ and $[U,D)$ for $B$. Here, $L,R,U,D$ are integers satisfying $1\le L\le R\le N+1$ and $1\le U\le D\le N+1$. Let $X$ and $Y$ be the sets of values occurring in these intervals, respectively: $$ X=\{A_i\mid L\le i

The input contains one or more test cases. The first line of the input contains an integer $T$ ($1\le T\le 10^4$), which is the number of test cases. The descriptions of the $T$ test cases follow, each in the format below. ```text 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 $N$, the common length of the four sequences ($1\le N\le 2\times 10^5$). The following four lines contain $N$ integers each and describe the sequences $A$, $B$, $V$, and $W$, respectively. The integers $A_i$ and $B_i$ satisfy $1\le A_i,B_i\le N$ for every $i$ ($1\le i\le N$). The integers $V_i$ and $W_i$ satisfy $1\le V_i,W_i\le 10^9$ for every $i$ ($1\le i\le N$). The sum of $N$ over all test cases does not exceed $6\times 10^5$.

Output $T$ lines. The $i$-th line should contain the maximum possible score for the $i$-th test case.

In the first test case, we can choose the interval $[1,3)$ of $A$ and the interval $[1,2)$ of $B$. More precisely, we can set $L=1$, $R=3$, $U=1$, and $D=2$. Their sets of values are $\{1,2\}$ and $\{3\}$, respectively, and they are disjoint. The score is $$ 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 $A$ and the entire interval $[1,4)$ of $B$. More precisely, $L=2$, $R=2$, $U=1$, and $D=4$.