Matrix Stability Adjustment

You are given an $n\times m$ matrix $G$, two permutations p and q (each of length $m$), and a constant $C$. An element $G_{i,j}$ is said to be out‐of-control if and only if \[ \vert G_{i,j} - G_{i-1,p_{j}}\vert > C \quad \text{and} \quad \vert G_{i,j} - G_{i+1,q_{j}}\vert > C, \] where indices are 1-indexed. By definition, all elements in the first and the last rows are safe.

In addition, you are given two sequences $A$ and $B$ of length $k$. There are $k$ types of operations: the $i$-th operation increases every element of some selected row by $A_i$ at a cost of $B_i$. You may use each type of operation an unlimited number of times, but for each row you can choose at most one operation (or do nothing). Moreover, you must ensure that for any two consecutive rows, at most one of them is operated on.

Your task is to choose an operation (or no operation) for each row (with the restriction that the first and the last rows must remain unchanged since they are automatically safe) so that every element of $G$ becomes safe, and report the minimum total cost required. It is guaranteed that a solution exists.

Note on safety: For any middle row $i$ ($2\le i\le n-1$) that is potentially modified by adding some value $x_i$ (which is $0$ if no operation is applied, or equal to one of $A_i$ if an operation is applied), its safety condition is that for every column $j$ ($1\le j\le m$), at least one of the following holds: \[ \left|\bigl(G_{i,j}+x_i\bigr) - \bigl(G_{i-1,p_{j}}+x_{i-1}\bigr)\right| \le C \quad \text{or} \quad \left|\bigl(G_{i,j}+x_i\bigr) - \bigl(G_{i+1,q_{j}}+x_{i+1}\bigr)\right| \le C. \]

Constraint on operations: If a row is operated (i.e. nonzero addition), then its two adjacent rows cannot be operated.

inputFormat

The input consists of several lines:

• The first line contains four integers $n$, $m$, $k$, and $C$.
• The next $n$ lines each contain $m$ integers, representing the matrix $G$.
• The next line contains $m$ integers representing the permutation $p$.
• The next line contains $m$ integers representing the permutation $q$.
• The next line contains $k$ integers representing the sequence $A$.
• The last line contains $k$ integers representing the sequence $B$.

Note: The matrix rows and permutations are 1-indexed. The first and the last rows of $G$ must always remain unchanged (i.e. no operation is applied on them).

outputFormat

Output a single integer: the minimum total cost required to make every element of $G$ safe.

sample

3 2 1 1
1 2
3 4
5 6
2 1
1 2
1
2

0