UVA774 Driving in City Squares

AllSquared市由许多著名的建筑师和工程师设计。这个城市位于一个 $n\times m$ 平方英里的矩形内。 街道是每英里均匀分布的水平分界线，大道是纵向分界线，也均匀分布在每一英里上。街道从北到南从 $0$ 开始编号，大道从西到东也是从 $0$ 开始编号。 下图（a）描绘了当 $n=8,m=11$ 时城市的布局。  城市也分为水平和竖直条带，这些条带的交点定义了城市子区域（县）。图（b）描绘了一个被分为12个县的城市。 每次汽车进入不同的县城时都要支付过境费。如果汽车起点在划定县的街道或大道上，则不收取任何费用。例如，在上图中，一辆起点是街道2和大道3，目标是街道2大道9的汽车只需支付大道6的县过境费。 你需要编写一个程序，具有以下输入： - 两个正整数 $n,m$ 指定城市尺寸； - 两个正整数 $h,v$ 分别指定水平和垂直条带的数量（对于图中的城市，$h=4，v=3$）; - $h-1$ 个整数 $s_1,s_2,……,s_{h-1}(1 \le s_i \le n-1)$，有县分界线的街道的编号（在上图中，这三条街道的编号为 $1,6,7$） - $v-1$ 个整数 $a_1,a_2,……,a_{v-1}(1 \le a_i \le m-1)$，有县分界线的大道的编号（在上图中，这两条大道的编号为 $3,6$） - 全市各县的过境费，即 $h\times v$ 个正整数： $p_{1,1},p_{1,2},...,p_{1,v}$ $p_{2,1},p_{2,2},...,p_{2,v}$ $. . .$ $p_{h,1},p_{h,2},...,p_{h,v}$ 其中 $p_{i,j}$ 是以 $a_{i-1}$（西），$a_{i+1}$（东），$s_{j-1}$（北），$s_{j+1}$（南）为界的县的流通费； - 两对正整数 $local_1=(str_1,av_1),local_2=(str_2,av_2)$（即起点和终点的坐标） 输出应该是从 $local_1$ 到 $local_2$ 所要支付的过境费总和的最小值。

输入可能有多组数据。每组数据以一个 `%` 隔开。每组数据的形式如下： ```cpp n m h v s{1} s{2} ... s{h-1} a{1} a{2} ... a{v-1} p{1,1} p{1,2} ... p{1,v} p{2,1} p{2,2} ... p{2,v} ... p{h,1} p{h,2} ... p{h,v} w{1} t{1} w{2} t{2} % ```

对每组输入，输出一行一个整数 $k$ 表示要支付的过境费总和的最小值。

$0 \lt h \le n \lt 100,0 \lt v \le m \lt 100;$ $1 \le s_i \le n-1;$ $1 \le a_i \le m-1;$ $0 \lt p_{i,j} \lt 10000;$ $0 \le w_1,w_2 \le n,0 \le t_1,t_2 \le m.$ 文件中的数字之间可以有任意数量的空格或空行。