题目描述

开辟新航路以后，欧洲的海上贸易日益繁荣，许多商人带领着他们的船队，在世界各地来往穿梭。这其中有位很有头脑的 XX 船长，他十分重视收集各港口的供需情报，并以此确定他的下一步计划，通过减少运输的时间来获取更多的利益。他的情报包括以下的内容：

1. 一幅完整的航海图。这其中包含了陆地、海洋以及各港口的位置。船只每次只能沿上下左右四个方向移动一格(不可移到陆地上和地图外,可移进港口)，且每次移动都需航行一天。
2. 各港口可供应的货物。当然，每种货物不可能到处都买的到，否则就用不着船队了。因此，规定每种货物最多只有 $20$ 个的港口供应。
3. 各港口需要的货物。

与情报 $2$ 不同的是，各港所需的货物是变化的，即 XX 船长是逐渐得到新情报的。同时，每当他得到一个新的货物需求 $(i,j)$（表示港口 $j$ 需要货物 $i$），他必须马上作出决策：选择几号船完成此任务。因为要计算出怎样最优是比较困难的，所以船长采取了这样一个近似的方法：找出「完成新任务所需时间」最少的船，将其用来完成新任务，若有多艘这样的船，则从中选择编号最小的（「完成新任务所需时间」包含两个过程：航行到一个供应货物 $i$ 的港口并上货和将货物 $i$ 运到港口 $j$ 并卸货，其中上货和卸货的时间忽略不计。因为上货港口的选择不同，所需的时间也会不同，所以，必须对上货的港口进行选择，使该船的「完成新任务所需时间」尽量短）。

XX 船长想要知道的是：他的所有船只共需多少时间来完成这些任务，即所有船只完成各自任务的时间和。

输入格式

第一行是是六个数 $N,M,port\_num,good\_num,ship\_num,start$，表示航海图的长、宽，以及港口总数、货物种类和船长拥有的船只数、所有船的初始位置（停泊的港口编号）。

以下 $N+1$ 行是一个 $N\times M$ 的矩阵，在矩阵中 $0,1,2$ 分别对应海洋、港口和陆地。港口的编号对应由上至下，由左至右（由上至下优先）的读入顺序，第一个读入的港口编号为 $1$，第二个读入的港口编号为 $2$……

第 $N+2$ 行到第 $N+port\_num+1$ 行按编号顺序给出了各港口供应的货物，其格式为：

$$\begin{matrix} n_1 & p_{1,1} & p_{1,2} &\dots & p_{1,n_1} \\ n_2 & p_{2,1} & p_{2,2} &\dots & p_{2,n_2} \\ \dots &\dots &\dots &\dots &\dots \\ n_i & p_{i,1} & p_{i,2} &\dots & p_{i,n_i} \\ \dots &\dots &\dots &\dots &\dots \\ n_{port\_num} & p_{port\_num,1} & p_{port\_num,2} &\dots & p_{port\_num,n_{port\_num}} \\ \end{matrix}$$

$n_i$ 是港口 $i$ 供应的货物总数，$p_{i,j}$ 是港口 $i$ 供应的第 $j$种货物编号。

第 $N+port\_num+2$ 行是一个数 $Total$，表示情报 $3$ 中获得的任务总数，以下 $Total$ 行按情报获得的时间给出了$Total$ 个任务，每个任务占一行，包含两个数 $i,j$，表示港口 $j$ 需要货物 $i$。

文件一行中相邻两数用一个或多个空格隔开。

输出格式

仅有一个数 $T$，是你的程序得出的所有船只完成各自任务的时间和。

样例输入

5 5 3 4 2 1
0 1 0 0 0
2 2 2 0 0
0 1 2 0 2
0 2 2 0 1
0 0 0 0 0
1 3
3 1 2 4
1 4
4
1 3
2 3
3 2
4 1

样例输出

54

数据规模与约定

对于 $100\%$ 的数据，$1\le N,M\le100$，$1\le port\_num\le 100$，$1\le good\_num \le 20$