#437. 【NFLSPC #2】火

题目类型:传统型 时间限制:50 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

有一个 $n \times n$ 的方格表 第 $i$ 行第 $j$ 列的格子燃烧完需要$a_{i,j}$的时间 然后会将火焰向四个方向传递

现在点燃了其中的$k$个格子 多长时间能烧完整个方格表?

请注意 格子不会被重复点燃 也不会因为任何原因增加燃烧速度


输入格式

第一行 一个整数 $n$ 满足 $1 \leq n \leq 300$

接下来$n$行 每行$n$个数字 代表方格表被完全燃烧需要的时间 $1 \leq a_{i,j} \leq 5$

接下来一行 一个整数$k$ 代表有几个格子初始被点燃 满足 $1 \leq k \leq 50$

接下来$k$行 每行两个整数$x,y$ 代表第$x$行第$y$列初始被点燃 满足$1 \leq x \leq n$,$1 \leq y \leq n$

保证初始被点燃的格子互不相同

输出格式

一行 一个整数$ans$ 表示需要$ans$时间将方格表燃烧完


样例一

input

2
21
52
1
1 1

output

7

样例二

input

2
21
52
2
1 2
2 1

output

5

请注意 为了节约评测时间 这题的时间限制和数据规模都进行了缩小

时间限制:$0.05\texttt{s}$

空间限制:$512\texttt{MB}$


$by\ \text{skyline}$