Quadratic Integer Programming

This problem is a well‐known NP problem – the quadratic integer programming problem. You are given an integer sequence of length n:

\( (x_1,x_2,\ldots,x_n) \)

where each \(x_i\) is an integer subject to two types of constraints:

1. Individual variable constraints: You are given a positive integer \(k\) (with \(3\le k \le 5\)) and for each \(1\le i\le n\) an interval \( [l_i, r_i] \) satisfying \(1\le l_i\le r_i\le k\). You must have \(l_i\le x_i\le r_i\) for every \(i\).
2. Pairwise constraints: You are given \(m\) triples \((p_j, q_j, b_j)\). For each \(1\le j\le m\) the sequence must satisfy \[ |x_{p_j} - x_{q_j}| \le b_j. \] Note that the pairs are unordered but when \(i\neq j\), the pair \((i, j)\) is considered different from \((j, i)\).

In addition, a weight function is defined. For any integer sequence \(\{p_1,p_2,\dots,p_n\}\) with each \(p_i\) in \([1,k]\), let \(c_i\) be the number of times the integer \(i\) appears in the sequence. Also, let \(G\) be the number of ordered pairs \((i, j)\) (with \(1\le i,j\le n\)) satisfying \(|p_i-p_j|\le 1\). Then the weight of the sequence is defined as

[ W(p_1, p_2, \ldots, p_n) = 10^6 \cdot G + \sum_{i=2}^{k-1} c_i \cdot v_i. ]

You will be given \(q\) queries. In each query, different values of \(v_2,v_3,\dots,v_{k-1}\) are provided. For each query, under the constraints above, you must find a sequence that maximizes the weight and output only the maximum weight.

Note: It is guaranteed that under the given constraints there exists at least one valid sequence.

inputFormat

The first line contains four integers \(n\), \(m\), \(q\), and \(k\) where \(3\le k\le5\). \(n\) is the length of the sequence, \(m\) is the number of pairwise constraints, and \(q\) is the number of queries.

The next \(n\) lines each contain two integers \(l_i\) and \(r_i\) representing the allowed interval for \(x_i\) (\(1\le i\le n\)).

The following \(m\) lines each contain three integers \(p_j\), \(q_j\), and \(b_j\) describing a pairwise constraint \(|x_{p_j} - x_{q_j}| \le b_j\) (\(1\le j\le m\)).

Then, \(q\) lines follow. Each query line contains \(k-2\) integers: \(v_2,v_3,\ldots,v_{k-1}\).

outputFormat

For each query, output the maximum weight achievable under the constraints. Each result should be printed on a new line.

sample

3 1 1 3
1 3
1 3
1 3
1 2 1
100

9000300