题目内容

你负责开发一个火灾监控预警系统。系统将监测区域建模为一个 $m \times n$ 的二维网格。每个位置要么是空地，用 0 表示；要么覆盖某种可燃物，用 1 到 $k$ 之间的正整数表示，该整数值就是该位置被点燃后需要持续燃烧的单位时间数。

初始时给出若干着火点，这些位置在 $0$ 时刻已经点燃。当一个可燃物位置被点燃后，必须先经过该位置对应的燃烧时间，火势才能向上下左右四个相邻位置传播。传播只能进入仍是可燃物的位置，不能进入空地。若某个位置可以被更早到达，则更新其最早点燃时间。多个着火点可能共同影响同一区域。

给定一个监控点，请计算它最早可能被点燃的时刻。若监控点本身是空地，或火势无法传播到该点，则返回 -1。

约束条件：

• 行数 $m$ 和列数 $n$ 满足 $0<m\le100$，$0<n\le100$。
• 初始着火点数量少于 5 个。
• 所有给出的坐标均在网格范围内，即 $0\le x<m$，$0\le y<n$。

输入描述

第一行包含两个整数 $m$ 和 $n$，表示二维监控区域 grids 的行数和列数。

接下来 $m$ 行，每行包含 $n$ 个整数，按行优先顺序描述 grids。其中 0 表示空地，正整数表示该位置可燃物的燃烧时间。

再接下来一行包含若干个整数，每两个整数构成一个着火点坐标 $(x, y)$，这些初始着火点坐标合称为 fires。该行包含的整数个数为偶数。

最后一行包含两个整数 $a$ 和 $b$，表示监控点坐标 monitor，其中 $a$ 为行号，$b$ 为列号。

输出描述

输出一个整数，表示火势最早传播到 monitor 坐标的时刻；如果 monitor 所在位置为 0（空地），或火势永远无法到达该位置，则输出 -1。

样例1

输入

3 3
5 1 1
1 1 1
1 1 1
0 0 2 0
0 2

输出

4

说明

监测区域行数为 3，列数为 3。两个初始火源分别为 (0,0) 和 (2,0)，监控点为 (0,2)。

从 (2,0) 出发的传播更早：(2,0) 在 0 时刻已经点燃，其燃烧时间为 1，所以 (1,0) 在 $0+1=1$ 时刻点燃。(1,0) 的燃烧时间也是 1，因此 (1,1) 在 $1+1=2$ 时刻点燃。(1,1) 的燃烧时间为 1，继续传到 (0,1) 的时刻是 $2+1=3$。(0,1) 的燃烧时间为 1，所以 (0,2) 在 $3+1=4$ 时刻点燃。

另一火源 (0,0) 的燃烧时间为 5，它到达 (0,1) 最早需要 $0+5=5$ 时刻，晚于从下方传来的 3 时刻，因此不会影响监控点的最早点燃时间。

所以监控点 (0,2) 的最早点燃时刻为 4。

样例2

输入

1 3
2 1 3
0 0
0 2

输出

3

说明

这是一个只有一行的边界情况，网格行数为 1，列数为 3。

初始火源 (0,0) 在 0 时刻点燃，其燃烧时间为 2，所以相邻的 (0,1) 在 $0+2=2$ 时刻点燃。(0,1) 的燃烧时间为 1，因此 (0,2) 在 $2+1=3$ 时刻点燃。

监控点 (0,2) 自身的燃烧时间为 3，但题目要求计算最早被点燃时刻，因此结果为 3。

样例3

输入

2 2
1 0
1 1
0 0
0 1

输出

-1

说明

监控点 (0,1) 对应的网格值为 0，表示该位置是空地。空地不会被点燃，因此无论火势如何传播，该点都不会有最早点燃时刻，直接输出 -1。

样例4

输入

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

输出

-1

说明

监控点 (2,2) 的网格值为 1，不是空地，但需要判断火势是否能够到达。

从火源 (0,0) 出发，(0,0) 的燃烧时间为 1，可以到达 (0,1) 和 (1,0)，到达时刻均为 $0+1=1$。

再看这两个格子：(0,1) 的相邻非零格只有 (0,0)，(1,0) 的相邻非零格也只有 (0,0)，其余相邻位置都是 0。因此火势被空地完全阻断，无法到达监控点 (2,2)，输出 -1。