Background

Being out of control might actually be being rational.

Problem Description

You are given an $n \times m$ matrix $G$ and two permutations $p, q$ of length $m$.

We say an element $G_{i,j}$ is out of control if and only if $\vert G_{i,j} - G_{i-1,p_j} \vert > C$ and $\vert G_{i,j} - G_{i+1,q_j} \vert > C$, where $C$ is a given constant. In particular, we define that no element in row $1$ and row $n$ is out of control no matter what.

Then you are also given two sequences $A$ and $B$, both of length $k$.

You have $k$ types of operations. The $i$-th operation adds $A_i$ to all elements in a chosen row, and costs $B_i$. Each operation type can be used any number of times, but for each row, you may either apply exactly one of these operation types or do nothing. Also, you must ensure that among any two adjacent rows, at most one row is operated on.

Find the minimum total cost to make every element in matrix $G$ not out of control (the testdata guarantees that a solution exists).

Input Format

The first line contains four integers $n, m, k, C$.

The next $n + 4$ lines are as follows: the first $n$ lines each contain $m$ numbers, describing matrix $G$. Lines $n + 1$ and $n + 2$ each contain $m$ numbers, describing permutations $p$ and $q$, respectively. The last two lines each contain $k$ numbers, describing sequences $A$ and $B$, respectively.

Output Format

Output one integer in a single line, representing the answer.

3 3 5 10
1 2 6
7 3 11
9 44 5
2 3 1
1 3 2
5 10 15 20 25
6 6 6 6 6

0

8 8 8 28
49 11 44 31 25 37 41 1 
29 38 46 21 21 17 45 47 
1 37 11 31 8 15 15 47 
21 47 15 6 11 9 40 28 
21 29 1 11 39 15 21 35 
26 20 3 38 1 41 27 21 
41 41 31 16 11 1 24 3 
33 15 23 26 7 47 49 8 
3 8 2 4 6 5 1 7 
7 5 8 3 6 1 4 2 
36 13 12 3 38 49 22 55 
20 24 2 30 26 25 17 25 

32

Hint

Sample Explanation #1

Obviously, for sample 1, performing no operation is enough to ensure that all elements are not out of control.

Sample Explanation #2

Apply operation $3$ on row $3$, and apply operation $4$ on row $7$. It can be proven that there is no better solution.

Constraints

"This problem uses bundled subtasks."

• $\operatorname{Subtask} 1(10\%)$: $n, m, k \leq 8$.

• $\operatorname{Subtask} 2(30\%)$: $m \leq 50, k \leq 100$.

• $\operatorname{Subtask} 3(20\%)$: $m \leq 50, k \leq 1000$.

• $\operatorname{Subtask} 4(40\%)$: no special restrictions.

For $100\%$ of the testdata: $3 \leq n \leq 50$, $1 \leq m \leq 300$, $0 \leq k \leq 2000$, $C, G_{i,j}, A_i, B_i \leq 10^6$.

The input size is large. Please use a fast input method.

Hint

• This problem is not strict about constant factors. If you feel your algorithm is just a bit too slow to pass the next Subtask, please do not get stuck optimizing meaningless constants, because that missing part may need a better algorithm to make up for it.

Translated by ChatGPT 5