{"raw_statement":[{"iden":"background","content":"失控的，或许反而是理智的。"},{"iden":"statement","content":"给定一个 $n \\times m$ 的矩阵 $G$ 和两个长度为 $m$ 的排列 $p,q$。\n\n我们称元素 $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$ 行的元素都不是失控的。\n\n此时再给定两个长度为 $k$ 的序列 $A$ 和 $B$。\n\n你将有 $k$ 种操作：其中第 $i$ 种操作是将某一行所有元素增加 $A_i$，这将会花费 $B_i$ 的代价。**每种操作可以使用的次数不限，但对于每一行，你只可以进行这些操作中的一种或不操作。并且，你必须保证任意相邻两行最多有一行进行操作。**\n\n请问要使得矩阵 $G$ 中所有元素均不失控，至少要花费的代价是多少（数据保证有解）？"},{"iden":"input","content":"第一行四个整数，分别为 $n,m,k,C$。\n\n接下来 $n+4$ 行，前 $n$ 行每行 $m$ 个数，表示矩阵 $G$，第 $n+1$ 和 $n+2$ 行每行 $m$ 个数，分别表示排列 $p$ 和 $q$，最后两行每行 $k$ 个数，分别表示序列 $A$ 和 $B$。"},{"iden":"output","content":"输出一行一个整数，表示答案。"},{"iden":"note","content":"#### 样例解释 #1\n\n显然对于样例一，不用进行任何操作就能保证所有元素均不失控。\n\n------------\n\n#### 样例解释 #2\n\n对第三行使用 $3$ 操作，对第七行使用 $4$ 操作即可。可以证明不存在更优的方案。\n\n------------\n\n#### 数据范围\n\n**「本题采用捆绑测试」** \n\n- $\\operatorname{Subtask} 1(10\\%)$：$n,m,k \\leq 8$。\n\n- $\\operatorname{Subtask} 2(30\\%)$：$m\\leq 50,k\\leq 100$。\n\n- $\\operatorname{Subtask} 3(20\\%)$：$m\\leq 50,k\\leq 1000$。\n\n- $\\operatorname{Subtask} 4(40\\%)$：无特殊限制。\n\n对于 $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$。\n\n**本题输入量较大，请用较快的输入方法。**\n\n------------\n\n#### 提示\n\n- 本题不卡常，如果你认为自己的算法差一点就能跑过下一个 Subtask 却没有跑过，那么请不要纠结于无意义的卡常，因为差的这一点可能需要更优秀的算法来弥补。"}],"translated_statement":null,"sample_group":[["3 3 5 10\n1 2 6\n7 3 11\n9 44 5\n2 3 1\n1 3 2\n5 10 15 20 25\n6 6 6 6 6","0"],["8 8 8 28\n49 11 44 31 25 37 41 1 \n29 38 46 21 21 17 45 47 \n1 37 11 31 8 15 15 47 \n21 47 15 6 11 9 40 28 \n21 29 1 11 39 15 21 35 \n26 20 3 38 1 41 27 21 \n41 41 31 16 11 1 24 3 \n33 15 23 26 7 47 49 8 \n3 8 2 4 6 5 1 7 \n7 5 8 3 6 1 4 2 \n36 13 12 3 38 49 22 55 \n20 24 2 30 26 25 17 25 ","32"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}