P8501 [NOI2022] Quadratic Integer Programming Problem

In this problem, you need to solve a famous NP problem—the quadratic integer programming problem. The quadratic integer programming problem has variables: you need to give an **integer** sequence $(x_1, x_2, \ldots, x_n)$ of length $n$ that satisfies all conditions below. The quadratic integer programming problem has constraints: the integer sequence you give must satisfy the following two types of constraints: 1. The first type constrains the value of each single variable: given a positive integer $k$ ($3 \leq k \leq 5$) and $n$ intervals $[l_i, r_i]$ ($1 \leq i \leq n$), where $1 \leq l_i \leq r_i \leq k$, your sequence must satisfy $\forall 1 \leq i \leq n$, $l_i \leq x_i \leq r_i$. 2. The second type constrains the values between variables: given $m$ triples $(p_i, q_i, b_i)$, your sequence must satisfy $\forall 1 \leq j \leq m$, $\lvert x_{p_j} - x_{q_j} \rvert \leq b_j$. The quadratic integer programming problem has an objective function: given $k-2$ objective parameters $v_2,v_3,\dots,v_{k-1}$ (**note that the index range is from $\boldsymbol{2}$ to $\boldsymbol{k-1}$**), for an integer sequence $\{p_1,p_2,\dots,p_n\}$ with value range $[1,k]$, let $c_i$ be the number of elements in the sequence whose value equals $i$, and let $G$ be the number of integer ordered pairs $(i, j)$ satisfying $1 \leq i,j \leq n$ and $|p_i-p_j|\leq 1$. **Note that when $\boldsymbol{i \neq j}$, $\boldsymbol{(i, j)}$ and $\boldsymbol{(j, i)}$ are different ordered pairs.** Define the **weight** of this sequence as $$ W(p_1, p_2, \ldots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i \text{。} $$ Your sequence needs to maximize its weight while satisfying the two types of constraints above. It is guaranteed that, under the given constraints, there exists a sequence that satisfies them. The quadratic integer programming problem does not have to include multiple queries, but we will give $q$ queries. Each query provides different weight parameters $v_2, v_3, \ldots, v_{k-1}$. For each query, you need to find a sequence that satisfies the constraints and maximizes the weight. To reduce the output size, you only need to output the weight of this sequence.

**This problem contains multiple test cases.** The first line contains a non-negative integer and a positive integer $C, T$, representing the test point ID and the number of testdata. $C = 0$ indicates that this set of data is a sample. For each testdata, the first line contains four integers $k, n, m, q$, describing the sequence value range, the sequence length, the number of constraints between variables, and the number of queries. The next $n$ lines each contain two integers $l_i, r_i$, describing the allowed value interval for each element in the sequence. The next $m$ lines each contain three integers $p_j, q_j, b_j$, describing one constraint between variables. The next $q$ lines each contain $k - 2$ non-negative integers $v_2, v_3, \ldots, v_{k - 1}$, describing the weight parameters of one query.

For each query of each testdata, output one line containing one integer, representing the maximum possible weight of the sequence.

**[Sample #1]** See `qip/qip1.in` and `qip/qip1.ans` in the attachment. This sample satisfies the property of test point $1$ in the Constraints. ---- **[Sample Explanation #1]** In the first testdata, the optimal sequence for both queries is $(1, 2, 2, 1, 3)$, where $c_2 = 2, G = 21$. ---- **[Sample #2]** See `qip/qip2.in` and `qip/qip2.ans` in the attachment. This sample satisfies the property of test point $3$ in the Constraints. ---- **[Sample Explanation #2]** In the first testdata, the optimal sequences for the two queries are $(4,4,3,3)$ and $(4,3,2,2)$. ---- **[Sample #3]** See `qip/qip3.in` and `qip/qip3.ans` in the attachment. This sample satisfies the property of test point $5$ in the Constraints. ---- **[Sample Explanation #3]** In the first testdata, one optimal sequence for the three queries is $(3, 3, 3, 3, 3)$, $(2, 2, 3, 3, 2)$, and $(3, 2, 4, 4, 2)$. ---- **[Sample #4]** See `qip/qip4.in` and `qip/qip4.ans` in the attachment. This sample satisfies the property of test point $2$ in the Constraints. ---- **[Sample #5]** See `qip/qip5.in` and `qip/qip5.ans` in the attachment. This sample satisfies the property of test point $4$ in the Constraints. ---- **[Sample #6]** See `qip/qip6.in` and `qip/qip6.ans` in the attachment. This sample satisfies the property of test point $8$ in the Constraints. ---- **[Sample #7]** See `qip/qip7.in` and `qip/qip7.ans` in the attachment. This sample satisfies the property of test point $14$ in the Constraints. ---- **[Sample #8]** See `qip/qip8.in` and `qip/qip8.ans` in the attachment. This sample satisfies the property of test point $17$ in the Constraints. ---- **[Constraints]** Let $\sum q$ be the sum of $q$ over all testdata in a single test point. For all test points, - $1 \leq T \leq 600$. - In the $i$-th ($1 \le i \le T$) testdata, $1 \leq n \leq \max(\frac{T}{i},2 \log_2 T)$. - $3 \leq k \leq 5$, $0 \leq m \leq 3n$, $1 \leq q,\sum q \leq 3 \times 10^5$. - $1 \leq l_i \leq r_i \leq k$. - $1 \leq p_j,q_j \leq n$, $0 \leq b_j