题目背景

失控的，或许反而是理智的。

题目描述

给定一个 $n \times m$ 的矩阵 $G$ 和两个长度为 $m$ 的排列 $p,q$。

我们称元素 $G_{i,j}$ 是失控的，当且仅当 $\vert G_{i,j} - G_{i-1,p_j} \vert > C$ 且 $\vert G_{i,j} - G_{i+1,q_j} \vert > C$，其中 $C$ 是给定的常数。特殊地，我们规定无论如何第 $1$ 行和第 $n$ 行的元素都不是失控的。

此时再给定两个长度为 $k$ 的序列 $A$ 和 $B$。

你将有 $k$ 种操作：其中第 $i$ 种操作是将某一行所有元素增加 $A_i$，这将会花费 $B_i$ 的代价。每种操作可以使用的次数不限，但对于每一行，你只可以进行这些操作中的一种或不操作。并且，你必须保证任意相邻两行最多有一行进行操作。

请问要使得矩阵 $G$ 中所有元素均不失控，至少要花费的代价是多少（数据保证有解）？

输入格式

第一行四个整数，分别为 $n,m,k,C$。

接下来 $n+4$ 行，前 $n$ 行每行 $m$ 个数，表示矩阵 $G$，第 $n+1$ 和 $n+2$ 行每行 $m$ 个数，分别表示排列 $p$ 和 $q$，最后两行每行 $k$ 个数，分别表示序列 $A$ 和 $B$。

输出格式

输出一行一个整数，表示答案。

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

提示

样例解释 #1

显然对于样例一，不用进行任何操作就能保证所有元素均不失控。

样例解释 #2

对第三行使用 $3$ 操作，对第七行使用 $4$ 操作即可。可以证明不存在更优的方案。

数据范围

「本题采用捆绑测试」

• $\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\%)$：无特殊限制。

对于 $100\%$ 的数据满足：$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$。

本题输入量较大，请用较快的输入方法。

提示

• 本题不卡常，如果你认为自己的算法差一点就能跑过下一个 Subtask 却没有跑过，那么请不要纠结于无意义的卡常，因为差的这一点可能需要更优秀的算法来弥补。