Minimize Maximum Weight Sum Meeting

You are given an n × m grid with integer weights (which may be negative) assigned to each cell. The cell in row i and column j is denoted by (i, j) and has weight \(a_{i,j}\). There are q persons located on the grid; the i-th person starts at cell (x_i, y_i) (starting positions need not be distinct).

A step consists of moving from cell (x,y) to one of its four neighbors: (x+1,y), (x-1,y), (x,y+1), or (x,y-1), provided that the destination cell remains within the grid boundaries \(1 \le x \le n\) and \(1 \le y \le m\). At any time, any number of persons can occupy the same cell.

For a given path, a person’s weight is defined as the sum of the weights of all cells visited (including the start and end points). If a cell is visited multiple times, its weight is counted each time. In particular, if a person does not move at all the weight is just that of the starting cell.

Define the total weight of a meeting as the maximum among the individual weights of the persons, when each person is allowed to take an arbitrary number of steps so that all persons finally meet at the same cell. Since a person may have the option to traverse a cycle with a negative total weight, his own achievable weight may be arbitrarily low (i.e. \(-\infty\)). If for a meeting cell every person can reduce his weight arbitrarily (using a negative cycle on his route), then the maximum of these (which is the total weight of the meeting) is \(-\infty\).

Your task is to choose a meeting cell and, for each person, choose a (possibly cyclic) path from his starting position to that cell such that the resulting total weight is minimized. Output the minimal total weight if it is finite; otherwise, if it is possible for every person to achieve an arbitrarily low weight for some meeting cell, output -Infinity (which means that no smallest total weight exists).

Note: Each move from a cell \(u\) to a neighboring cell \(v\) adds \(a_v\) (the weight of the destination cell) to the cost, and the starting cell’s weight is counted once.

inputFormat

The first line contains three integers: n, m and q — the number of rows, columns, and persons respectively.

The next n lines each contain m integers. The j-th integer in the i-th line is \(a_{i,j}\), the weight of cell (i, j).

The next q lines each contain two integers xi and yi, representing the starting cell coordinates for the i-th person.

outputFormat

If there is a meeting cell for which every person can achieve an arbitrarily low weight (i.e. using a negative cycle) then output -Infinity (without quotes). Otherwise, output the minimal total weight achievable, where the total weight is defined as the maximum over persons of the path sum they accumulate.

You can assume that there is at least one cell reachable by all persons.

sample

2 2 1
1 2
3 4
1 1

1