题目描述

牛牛，小 D 和小 R 来到了第 2017 届 OI 游戏比赛。

游戏规则：三人一组，在棋盘上玩跳房子。这个棋盘是 $n\times n$ 大小的，每个格子要么是红色，要么是黄色。每个格子都有一个分数值 $f_{i,j}$ （可以为负）。

牛牛，小 D 和小 R 的机器人（姑且叫 $A,B,C$ 吧）刚开始都在棋盘的左上角。每个机器人的跳跃距离为 $d$。如果花了 $g$ 枚金币，那么每个机器人可以跳跃的距离范围就在 $[\max(1,d-g),d+g]$ 之间。

每次机器人可以选择往正下或者往正右跳。每跳到一个格子就会得到这个格子的分数值。如果跳之前和跳之后的格子同色，那么会额外获得 $1$ 分。每个机器人的游戏可以在任意时候结束。各个机器人的游戏互不干扰。

最终成绩 $S=A\times 20\%+B\times 30\%+C\times 50\%$。如果你得到了 $S$ 分，你将会获得 $\lfloor S\rfloor$ RMB。

牛牛，小 D 和小 R 理所当然的在一组参加比赛。小 D 是一名图书管理员，他有数不完的金币。现在小 D 的图书馆没多少书，但有很多读者前来借书。他们如果借不到书会不满意，你必须要贿赂用 RMB 说服他们，所以小 D 要让 $S$ 很大，大到可以说服所有不满意的读者，否则图书馆的口碑变差了，没人来看书就完了。

现在图书馆里已经有 $m$ 本书，每本书都有一个编码 $c_i$。还有 $q$ 个读者，想要看编码以 $b_i$ 结尾的书，不满意的话需要 $w_i$ 元说服。现在牛牛，小 D 和小 R 想问你，要想满足所有读者，至少要在比赛中花多少金币？（也就是求 $g$ 的最小值）

输入格式

第一行四个整数 $n,m,q,d$，分别表示棋盘的大小，图书馆里原有的书数量，图书馆里的读者数量，以及一开始机器人的跳跃距离。
接下来 $m$ 行，每行一个数 $c_i$ 表示第 $i$ 本书的编码。
接下来 $q$ 行，每行三个数 $l_i,b_i$ 和 $w_i$，分别表示 TA 需要的需求码长度，TA 的需求码和说服 TA 需要的 RMB。保证 $b_i$ 没有前导 0 。
接下来 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 列的数 $x_{i,j}$ 表示在棋盘第 $i$ 行第 $j$ 列的格子的颜色，$1$ 表示红色，$2$ 表示黄色。
接下来 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 列的数 $f_{i,j}$ 表示在棋盘第 $i$ 行第 $j$ 列的格子的分数值。保证棋盘的左上角， $f_{1,1}=0$。

输出格式

一行， $g$ 的最小值，也就是需要花的金币的最小值。如果无论如何都无法满足所有读者，输出 $-1$。

样例 1

5 5 7 2
1
12
123
1234
12345
1 2 1000
2 12 2000
2 13 15
3 123 1234
3 124 5
4 1234 3214
4 1235 10
1 2 1 2 2
1 1 2 1 1
2 1 2 2 2
1 1 1 1 1
1 2 2 1 2
0 3 5 1 2
1 4 5 2 4
6 7 3 2 6
1 2 8 9 4
3 1 5 2 6

1

首先要让所有读者满意至少需要 $30$ RMB。

花了 $1$ 金币后，下面是一种可行方案：（虽然不止一种）

A 机器人： $0-1-1-8-9-4-6$ 得分 $34$

B 机器人：$0-1-4-2-4-6-4-6$ 得分 $32$

(第 4 个数 2 在第 3 个数 4 右边第 2 个，不是下面的）

C 机器人：$0-3-5-2-4-6-4-6$ 得分 $30$

$S=\lfloor34 \cdot 20\%+32 \cdot 30\%+30 \cdot 50\%\rfloor=\lfloor6.8+9.6+15\rfloor=\lfloor31.4\rfloor=31\geq 30$ ，所以花 $1$ 金币就够了。

而不花金币是走不出来的，所以输出 $1$。

5 5 7 5
1
12
123
1234
12345
1 1 1000
2 12 2000
2 13 15
3 123 1234
3 124 5
4 1234 3214
4 1235 10
1 2 1 2 2
1 1 2 1 1
2 1 2 2 2
1 1 1 1 1
1 2 2 1 2
0 -3 5 1 2
1 4 5 2 4
6 -7 3 2 -6
1 2 -8 -9 4
-3 1 -5 2 -6

-1

数据范围与提示

不一定要走到右下角再结束！随时可以结束！并且三个机器人的路线可以相同！

对于测试点 $1,2,3$，$1\leq n\leq 10^1$。

对于测试点 $4,5,6$，$1\leq n\leq 10^2$。

对于测试点 $7,8,9,10$，$1\leq n\leq 10^3$。

对于测试点 $1,3,9$，保证所有格子同色。

对于测试点 $1,2,4$，$1\leq m,q\leq 10^1$。

对于测试点 $5,7,8$，$1\leq m,q\leq 10^2$。

对于测试点 $3,6,9,10$，$1\leq m,q\leq 10^3$。

对于所有测试点，$1\leq c_i,b_i\leq 10^9-1,1\leq l_i\leq 9,1\leq w_i\leq 10^9,0\leq |f_{i,j}|\leq 10^9,1\leq x_{i,j}\leq 2,1\leq d\leq n$。