Chase in the Cloud Dream Garden

Duoyi is chasing GuoJi in the mystical Cloud Dream Garden, which is represented as an n×m grid. The cell in the i-th row and j-th column is denoted as \((i,j)\). Each cell \((i,j)\) either contains a positive integer height \(h_{i,j}\) or is an obstacle (in which case \(h_{i,j}=0\), and the cell is not accessible). Additionally, there are k specified cells where sword flight is allowed.

Initially, Duoyi starts at cell \((1,1)\) and she must reach cell \((n,m)\) as quickly as possible. Duoyi can perform one of the following actions per unit time when standing on any cell \((i,j)\):

• Adjacent Move: Move to one of the four adjacent cells \((i-1,j)\), \((i+1,j)\), \((i,j-1)\), \((i,j+1)\) provided the cell is within bounds and is not an obstacle.
• Sword Flight: If the current cell is one of the designated flying cells, Duoyi can fly to any other flying cell that currently has the same height as her current cell. This move costs 1 unit of time.
• Magic Change: Regardless of the cell type, Duoyi can cast a magical spell to change the height \(h_{i,j}\) of the cell she is in to any positive integer of her choice. This move also costs 1 unit of time. (Note that the height change is permanent for that cell.)

For teleportation (sword flight) between two flying cells \(u\) and \(v\):

• If \(h_u = h_v\) (i.e. the heights are equal), Duoyi may fly directly with a cost of 1.
• If \(h_u \neq h_v\), she can first use magic at \(u\) to change \(h_u\) to \(h_v\) (cost 1) and then fly (cost 1), making the total cost 2.

Your task is to help Duoyi find the minimum time required to reach cell \((n,m)\) using any sequence of allowed moves.

Note: The grid indices are 1-based. It is guaranteed that cells \((1,1)\) and \((n,m)\) are accessible (i.e. not obstacles).

inputFormat

The first line contains three integers n, m, and k — the number of rows, columns, and the number of cells where sword flight is allowed.

The next n lines each contain m integers. The j-th number in the i-th line represents \(h_{i,j}\). A value of 0 means the cell is an obstacle, while any positive integer indicates the height of that cell.

The following k lines each contain two integers r and c, representing that the cell (r, c) is a designated cell where sword flight is allowed.

outputFormat

Output a single integer: the minimum time (in units) required for Duoyi to reach cell \((n,m)\) from cell \((1,1)\). If it is impossible to reach the destination, output -1.

sample

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

3