Minimum Cost City Wall Construction

Rectos Island is frequently threatened by floods and pirate attacks. In order to protect all the villages on the island, the king has decided to build a city wall. The island is modeled as a square grid, and each village occupies one cell. In particular, the capital village is located at the northwest corner (the top‐left cell).

The wall must be built along the grid lines. The design procedure is as follows: starting from one of the two grid lines emanating from the top‐left corner, each subsequent segment of the wall is built contiguous to the previous one (i.e. they share an endpoint) until the wall eventually returns to the top–left corner. Note that if a grid line carries more than one segment of the wall, its cost is counted as many times as the segments placed on it.

Each segment of the grid line has an associated building cost. The total cost is the sum of the costs of all segments used. The wall must be constructed so that no village (without crossing the wall) can be reached from the outside of the grid.

Your task is to help the king by finding the minimum cost for constructing such a wall.

Formulation as a Minimum Cut Problem: One way to view the problem is to model the grid cells as nodes in a graph. Two adjacent cells share an edge corresponding to the grid segment between them; the capacity (or cost) of that edge is given by the cost on that segment. In addition, every cell adjacent to a boundary has an extra edge connecting it to the "outside" (source) with capacity equal to the cost for building a wall on that boundary segment. Finally, for every village cell (including the capital) we add an edge with infinite capacity connecting the cell to a sink. Then the minimum cost required to prevent any path from the outside (source) to any village (sink) is equal to the minimum cut between the source and the sink.

Note: In the wall construction, if a grid segment is used multiple times, its cost is counted that many times.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 50, 1 ≤ m ≤ n*n), where n is the side length of the square grid and m is the number of villages. (The capital village is always at cell (1,1)).

The next m lines each contain two integers r and c (1 ≤ r, c ≤ n) representing the row and column of a village.

This is followed by n+1 lines. Each of these lines contains n integers. The i-th line (0-based indexing for i) represents the cost to build a wall on the horizontal grid segments in the i-th horizontal row of grid lines. In particular, the first line represents the top boundary and the last line represents the bottom boundary of the grid.

Then there are n lines, each containing n+1 integers. The j-th line represents the cost for the vertical grid segments in that row. The first integer in each line is the cost for the left boundary and the last integer is for the right boundary.

All costs are positive integers.

outputFormat

Output a single integer — the minimum total cost of constructing the wall so that no village is reachable from outside without crossing the wall.

sample

2 1
1 1
1 2
3 4
5 6
7 8 9
10 11 12

19