Peg Solitaire: Minimum Remaining Chesspieces

Peg Solitaire is a single-player board game played on a chessboard with \( n \) rows and \( m \) columns. Initially, there are \( k \) chesspieces placed on the board. The board configuration is given by \( k \) pairs of coordinates. Every cell on the board is either empty or contains one chesspiece.

During the game, a move is performed by selecting a chesspiece, jumping it over an adjacent chesspiece into an empty cell, and then removing the jumped chesspiece. More formally, if a chesspiece is located at \( (i,j) \), the following four types of moves can be performed:

\[ \begin{array}{l} \text{Up: } (i,j) \rightarrow (i-2, j) \quad \text{if } (i-1,j) \text{ has a piece and } (i-2,j) \text{ is empty},\\[6pt] \text{Down: } (i,j) \rightarrow (i+2, j) \quad \text{if } (i+1,j) \text{ has a piece and } (i+2,j) \text{ is empty},\\[6pt] \text{Left: } (i,j) \rightarrow (i, j-2) \quad \text{if } (i,j-1) \text{ has a piece and } (i,j-2) \text{ is empty},\\[6pt] \text{Right: } (i,j) \rightarrow (i, j+2) \quad \text{if } (i,j+1) \text{ has a piece and } (i,j+2) \text{ is empty}. \end{array} \]

You may perform any number of moves (possibly zero). Your task is to determine the minimum possible number of chesspieces remaining on the board after a sequence of valid moves.

inputFormat

The first line of input contains three integers \( n \), \( m \), and \( k \) (the number of rows, columns, and initial chesspieces, respectively).

Each of the next \( k \) lines contains two integers \( r \) and \( c \) (1-indexed), representing the row and column positions of a chesspiece. All other cells are initially empty.

outputFormat

Output a single integer representing the minimum number of chesspieces that can remain on the board after performing any sequence of valid moves.

sample

3 3 8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3

1