#1060. 考试作弊

内存限制:128 MiB 时间限制:1000 ms 输入文件:cheat.in 输出文件:cheat.out
题目类型:传统 评测方式:文本比较
上传者: Handwer

题目描述

众所周知,学钧灰常机智.

然而,机智的人还是要考试的,学钧面对的就是一次大考.

可是学钧并不像学基那样可以逢考必过,所以他要寻求作弊的好方法.

这一场信息技术考试在一个 n*m 的教室中举行,而学钧唯一会的作弊方法就是老掉牙的——前后左右传答案.而这显然需要许多人的配合,已知贿赂一个位置为(i,j)的人配合学钧作弊的代价为cost[i][j](下标从 1 开始).为了保证作弊安全,所有作弊的人都必须在一个四连通块中.

学钧经过事先调查,得知了 K 个人信息技术非常好,他希望这 K个人一定要参加这次作弊计划.

现在请你计算一下学钧完成这次作弊计划的最小代价.

输入格式

输入第一行为三个正整数n,m,K,表示教室的大小为n*m,有K个人是作弊计划的目标.

接下来 n 行,每行 m 个正整数,第 i 行第 j 个数表示贿赂的代价cost[i]j.

接下来一行两个正整数 x,y 表示学钧的位置.

最后 K 行,每行两个正整数 x,y,表示目标的位置.

保证目标的位置和学钧的位置均不相同且均在范围内.

输出格式

输出一个正整数,表示作弊的最小代价.

样例

样例 1

输入样例

3 3 1 
1 100 3 
1 2 3 
1 2 3 
1 2 
3 3 

输出样例

7

样例 2

输入样例

4 5 3 
1000 4 5 1 2 
2 2 2 2 7 
2 4 1 4 5 
3 2 1 7 1 
1 1 
1 5 
4 1 
4 4 

输出样例

25

数据范围与提示

constraints