Master Oogway#10673
When Barish enrolled at the Massachusetts Institute of Technology, he took his turtle Oogway with him. Master Oogway is an exceptionally smart turtle, and like his owner Barish, he enjoys solving algorithmic problems wherever he goes. While walking around the MIT campus, Barish and Oogway came across a rectangular area of size n \times m, divided into cells. In this area, the top-left cell is denoted as , and the bottom-right cell is denoted as . To test Oogway's intelligence, Barish placed coins on certain cells, and Oogway, starting from cell , must collect these coins by moving only right or down. It is clear that in some cases it is impossible to collect all coins in one trip. Therefore, they come to this area every day, and Oogway, starting from cell , collects a certain number of coins each day. Barish is interested in the minimum number of days Oogway needs to collect all the coins.
The first line contains two integers (1 \leq n \leq 10^{9}) and (1 \leq m \leq 10^{9}) - the number of rows and columns in the rectangular area, respectively. The second line contains an integer (1 \leq q \leq 10^{5}) - the number of coins. Each of the next lines contains the coordinates of the cells where coins are placed, given as two integers x_i (1 \leq x_i \leq n) and y_i (1 \leq y_i \leq m). All coins are located in different cells.
Print a single integer - the minimum number of days required to collect all coins.
Example 1
The area given in the example:
Oogway's movements on the first day can look as shown below:
Oogway's movements on the second day can look as shown below:
The problem consists of the following subtasks:
