Problem C
Dansgólf

Example of a dancefloor

Haven’t you seen the new dancefloor at Vestur? It’s the hottest thing in town these days and the youth wait in long queues to get a spot at the dancefloor to dance!

Despite the high traffic recently, business hasn’t been going well at Vestur and they’re looking for all kinds of ways to save money. For example it’s fairly expensive to light up the dancefloor, so they are wondering if they can turn off some of the lights. The lights have to be on where people are dancing though of course.

The dancefloor is like on the image to the right. It consists of $N$ rows and $M$ columns. Each light lights up an entire diagonal of the dancefloor and each light has its own color.

Vestur has now asked you for help. They give you a list of all the tiles on the dancefloor that contain dancing people and ask you to find what the least number of lights they have to keep on is.

Input

The first line of the input contains three integers $N, M, K$ where $N$ denotes the number of rows, $M$ denotes the number of columns and $K$ denotes the number of tiles with people dancing onthem. Then there are $K$ lines, each containing two integers $x, y$, $1 \leq x \leq N$ and $1 \leq y \leq M$ which denotes that people are dancing on tile $(x,y)$. No tile will be listed twice.

Output

Output the least number of lights that have to be turned such that all tiles with people dancing on them are lit up.

Explanation of sample 1

Figure 1: Sample 1

As can be seen on Image 1 two lights need to be turned on to light up all the tiles with dancers (which are denoted by red dots).

Scoring

The solution will be tested on input data of varying difficulty and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

4 4 3
3 1
1 2
3 4

2

4 1 4
1 1
2 1
3 1
4 1

4