当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

开拓者正在帮助振兴金人巷，现在他被一个物流规划问题难倒了。

金人巷可以看作一个 $n \times m$ 的方格图，有些方格上有障碍物，另外有一些方格上有额外收益，还有一些方格上什么也没有。其中有 $k$ 个方格是物流起点，另有 $k$ 个方格是物流终点，保证这些方格上都没有障碍物，且这 $2k$ 个方格互不相同，起点和终点没有对应关系。一条合法的物流，必须从一个物流起点开始，每次走到一个相邻（两个方格相邻当且仅当它们拥有公共边）的没有障碍物的方格，最终到一个物流终点结束。一条物流的初始评分为 $100$ 分，每经过一个方格（物流经过的点包括起点和终点）扣 $1$ 分，如果经过的方格上有额外收益，则给评分加 $1$ 分。

由于物流所使用的机巧鸟不太聪明，所以任意两条物流都不允许经过同一个方格。请你合理进行物流规划，物流可以有任意条（一条都没有也是可以的），求出所有物流的评分总和的最大值。

输入格式

第一行三个正整数 $n, m, k$ $(n,m \leq 30, k \leq 10)$，含义如题目描述。

接下来共 $n$ 行，每行 $m$ 个用空格隔开的整数，其中第 $i$ 行第 $j$ 个整数 $a_{i,j}$ $(-1 \leq a_{i,j} \leq 1)$，用于描述方格图第 $i$ 行第 $j$ 列的状态。

• 若 $a_{i,j} = -1$，则表示该位置有障碍物；
• 若 $a_{i,j} = 1$，则表示该位置有额外收益；
• 若 $a_{i,j} = 0$，则表示该位置什么也没有。

接下来共 $k$ 行，每行两个正整数 $x_i, y_i$ $(1 \leq x_i \leq n, 1 \leq y_i \leq m)$，表示第 $x_i$ 行第 $y_i$ 列的方格是物流起点。

接下来共 $k$ 行，每行两个正整数 $p_i, q_i$ $(1 \leq p_i \leq n, 1 \leq q_i \leq m)$，表示第 $p_i$ 行第 $q_i$ 列的方格是物流终点。

输出格式

仅一行一个整数，表示物流评分总和的最大值。

3 3 2
1 -1 1
1 1 1
1 0 1
2 1
3 3
2 2
1 3

200

8 8 3
1 0 0 -1 0 0 1 -1
0 -1 1 -1 -1 -1 1 0
-1 1 0 1 1 -1 1 -1
0 0 1 0 -1 0 1 -1
0 0 1 -1 -1 0 0 0
-1 1 -1 1 1 1 1 -1
1 0 1 0 0 1 0 1
-1 0 0 0 -1 0 -1 1
7 1
5 3
5 2
5 1
7 4
1 6

196