Catholic University Loves Cats

Time limit2sMemory limit512 MB

Summary

Given a huge grid, start (0,0) and target (N,M), count the maximum number of cat points lying on some shortest monotone lattice path from start to target.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Prefix sum, Combinatorics
Solved: No attempts yet

Problem

Catholic University has many cats. Kuki, one of the many students who love cats, always came to school earlier than his class time to feed them. Unfortunately, now that he is a fourth-year student, he is busy preparing for employment and can no longer spend much time taking care of the cats.

Still, Kuki loves cats, so among the various routes from the school's main gate to Dasol Hall, where his class is, he wants to find the route on which he can meet and feed the most cats. Kuki moves to Dasol Hall only in the up, down, left, and right directions, and each move takes 1 unit of time. The time spent feeding a cat is short enough to ignore. Kuki can avoid being late for class only if he moves from the main gate to Dasol Hall as fast as possible. Help kind-hearted Kuki feed as many cats as possible without being late for class.

Catholic University is a rectangle of size N × M, the main gate is at (0, 0), and Dasol Hall is at (N, M).

Input

The first line gives the integers N, M (0 ≤ N, M ≤ 1,000,000,000).

The second line gives the integer T (0 ≤ T ≤ 100,000), the number of cats.

Each of the next T lines gives the integers r, c (0 ≤ r, c ≤ 1,000,000,000), the position of a cat. No two coordinates coincide, and cats may exist outside Catholic University.

Output

On the first line, print the maximum number of cats that can be fed before class time.

Examples2

Example 1
Input
```
5 6
6
0 0
1 6
2 2
2 1
4 3
5 6
```
Expected output
```
5
```
Example 2
Input
```
100 100
3
101 101
102 100
100 100
```
Expected output
```
1
```