Cave Support Optimization

The cave is represented by an \( N\times N \) grid. Each cell is denoted by \( (X,Y) \) with \(1 \le X,Y \le N\). Here \( X \) denotes the row (from top to bottom) and \( Y \) denotes the column (from left to right). Thus, \((1,1)\) is the top‐left, \((1,N)\) is the top–right, \((N,1)\) is the bottom–left and \((N,N)\) is the bottom–right cell.

For every cell, if \( X+Y \) is odd, it has an instability value \( V_{X,Y} \) (given in the input). If \( X+Y \) is even, its instability is \(0\). Moreover, some cells have already collapsed. Collapsed cells (there are \(K\) of them) are unavailable – you cannot place a pillar on them or occupy them – and their instability is also considered to be \(0\), even if \( X+Y \) is odd.

ZRQ has \(M\) L–shaped pillars that can support the cave. Each pillar is of infinite strength. When a pillar is placed, if the pillar supports a cell, the instability of that cell will become \(0\). However, each pillar is L–shaped and occupies three cells: the supported cell (the "corner") and two adjacent cells that form the L shape. The pillar can be placed in any of the 4 possible L orientations. For a pillar placed with its supported (corner) cell at \( (x,y) \), the 4 possible placements are as follows (provided the cells exist):

• Down–Right: occupies \( (x,y) \), \( (x+1,y) \) and \( (x,y+1) \).
• Down–Left: occupies \( (x,y) \), \( (x+1,y) \) and \( (x,y-1) \).
• Up–Right: occupies \( (x,y) \), \( (x-1,y) \) and \( (x,y+1) \).
• Up–Left: occupies \( (x,y) \), \( (x-1,y) \) and \( (x,y-1) \).

Important: A pillar only supports (i.e. reduces the instability of) its corner cell. The other two cells that it occupies do not have their instability reduced. Also, the placement of a pillar is valid only if all three occupied cells are not collapsed and no two pillars occupy the same cell. You may choose to place fewer than \(M\) pillars.

The initial total instability of the cave is the sum of \( V_{X,Y} \) for all cells with \( X+Y \) odd (ignoring collapsed cells, whose instability is \(0\)). By placing pillars, you can reduce the instability of some cells to \(0\). Find the minimum possible total instability of the cave after optimally placing at most \(M\) pillars.

Mathematically, if \( S \) is the set of cells with \( X+Y \) odd that are not collapsed, and if you can support a subset \( T \subseteq S \) (with at most \(M\) supports) by valid pillar placements, then you want to minimize

[ \text{Total Instability} = \sum_{(X,Y)\in S}V_{X,Y} - \sum_{(X,Y)\in T}V_{X,Y}. ]

inputFormat

The input begins with a line containing three integers \( N \), \( M \) and \( K \) \( (1 \le N \le \text{small},\; 0 \le M \le N^2,\; 0 \le K \le N^2) \) representing the size of the grid, the number of pillars, and the number of collapsed cells respectively.

The next \( K \) lines each contain two integers \( X \) and \( Y \) (\(1 \le X,Y \le N\)), indicating the coordinates of a collapsed cell.

Then, for each cell in the grid in row–major order (from \( X=1 \) to \( N \), and for each row from \( Y=1 \) to \( N \)), if \( X+Y \) is odd, an integer \( V_{X,Y} \) is given denoting its instability. (Cells with \( X+Y \) even are not assigned a value as their instability is \(0\)).

outputFormat

Output a single integer: the minimum total instability of the cave after placing at most \(M\) pillars optimally.

sample

3 1 0
5
6
7
4

15