| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $0$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
开拓者正在帮助振兴金人巷，现在他被一个物流规划问题难倒了。
金人巷可以看作一个 n × m 的方格图，有些方格上有障碍物，另外有一些方格上有额外收益，还有一些方格上什么也没有。其中有 k 个方格是物流起点，另有 k 个方格是物流终点，保证这些方格上都没有障碍物，且这 2k 个方格互不相同，起点和终点没有对应关系。一条合法的物流，必须从一个物流起点开始，每次走到一个相邻（两个方格相邻当且仅当它们拥有公共边）的没有障碍物的方格，最终到一个物流终点结束。一条物流的初始评分为 100 分，每经过一个方格（物流经过的点包括起点和终点）扣 1 分，如果经过的方格上有额外收益，则给评分加 1 分。
由于物流所使用的机巧鸟不太聪明，所以任意两条物流都不允许经过同一个方格。请你合理进行物流规划，物流可以有任意条（一条都没有也是可以的），求出所有物流的评分总和的最大值。
第一行三个正整数 n, m, k (n, m ≤ 30, k ≤ 10)，含义如题目描述。
接下来共 n 行，每行 m 个用空格隔开的整数，其中第 i 行第 j 个整数 ai, j( - 1 ≤ ai, j ≤ 1)，用于描述方格图第 i 行第 j 列的状态。若 ai, j = - 1，则表示该位置有障碍物；若 ai, j = 1，则表示该位置有额外收益；若 ai, j = 0，则表示该位置什么也没有。
接下来共 k 行，每行两个正整数 xi, yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m)，表示第 xi 行第 yi 列的方格是物流起点。
接下来共 k 行，每行两个正整数 pi, qi (1 ≤ pi ≤ n, 1 ≤ qi ≤ m)，表示第 pi 行第 qi 列的方格是物流终点。
3 3 2
1 -1 1
1 1 1
1 0 1
2 1
3 3
2 2
1 3
200