404519: GYM101522 K Knights

The King of Byteland owns an army of well-trained knights. One day, he decides to attack Hackerland. Hackerland can be described as a grid with N rows and M columns. The cell on the i-th row, j-th column is called cell (i, j) for convenience. The north-west corner is (1, 1) while the south-east corner is (N, M).

In order to win, the Byteland army must occupy all cells with knights. Now, the King of Byteland has carefully planned the attack. The attack can be divided into two phases.

In the first phase, a number of knights are sent to some specific cells of Hackerland.

After the first phase has ended, the second phase begins. In the second phase, The knights will start attacking the land of Hackerland. Their only way to attack is as follows: If at any moment, there are two knights on the same row or the same column, then all unoccupied cells between the two knights will be under attack, and more knights will be immediately sent to occupy these cells. This phase will end when no more cells can be occupied.

Please note that the knights are not allowed to move once they are sent to Hackerland.

In the following graph, the cells (2, 7), (4, 3), (5, 7) and (8, 3) are occupied in the first phase.

When the second phase starts, the cells between (4, 3) and (8, 3), (2, 7) and (5, 7) are under attack, and then occupied by other knights. Afterwards, the cells between (4, 3) and (4, 7), (5, 3) and (5, 7) will also be occupied. The second phase will end after this as no more cells can be occupied.

The attack is currently in the first phase. K cells of Hackerland are already occupied under the command of the King. You, the leader of the knights, are going to send some more knights (possibly none) to some cells of Hackerland of your choice before the second phase starts.

On one hand, you have to send enough knights to ensure that at the end of the war, all cells are occupied. On the other hand, you have to send as few knights as possible to minimize the chance of being discovered by the army of Hackerland. Your task is to find out the minimum number of knights to be sent.

The first line contains three integers: N, M and K. (1 ≤ N, M ≤ 100, 0 ≤ K ≤ N·M)

The next K lines each contains two integers: x and y, which means a knight was sent by the King to occupy cell (x, y). (1 ≤ x ≤ N, 1 ≤ y ≤ M)

No any two knights are sent to the same cell.

Output an integer, the minimum number of extra knights to be sent, on a single line.

1 1 0

1

2 2 0

4

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

0