가톨릭대는 고양이를 사랑해

시간 제한2초메모리 제한512 MB

요약

거대한 격자에서 (0,0)에서 (N,M)까지 가는 최단 경로 위에 놓인 고양이 점의 개수의 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 누적 합, 조합론
정답자: 아직 제출이 없습니다

문제

가톨릭대학교에는 고양이가 많다. 고양이를 사랑하는 학생 중 한 명인 쿠기는 수업 시간보다 항상 일찍 등교해서 고양이 밥을 챙겨주곤 했다. 안타깝게도 4학년이 된 쿠기는 취업 준비에 바빠 고양이를 챙기는 데 많은 시간을 쏟을 수 없게 되었다.

그래도 고양이를 사랑하는 쿠기는 학교 정문에서 수업이 있는 다솔관까지 가는 여러 경로 중에서 가장 많은 고양이를 만나 밥을 챙겨 줄 수 있는 경로를 찾고 싶어 한다. 쿠기는 다솔관까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동하는 데 1만큼 걸린다. 고양이에게 밥을 주는 시간은 무시할 수 있을 정도로 짧다. 쿠기는 정문에서 다솔관까지 가장 빠르게 움직일 때만 수업에 늦지 않을 수 있다. 마음 착한 쿠기가 수업에 늦지 않으면서 최대한 많은 고양이의 밥을 챙길 수 있도록 도와주자.

가톨릭대는 크기가 N × M인 직사각형이고, 정문은 (0, 0), 다솔관은 (N, M)에 있다.

입력

첫 번째 줄에 정수 N, M(0 ≤ N, M ≤ 1,000,000,000)이 주어진다.

두 번째 줄에 고양이의 수를 나타내는 정수 T(0 ≤ T ≤ 100,000)가 주어진다.

세 번째 줄부터 T개의 줄에 고양이의 위치를 나타내는 정수 r, c(0 ≤ r, c ≤ 1,000,000,000)가 주어진다. 두 개 이상의 좌표가 중복되는 경우는 없고, 가톨릭대 밖에 고양이가 존재할 수 있다.

출력

첫 번째 줄에 수업 시간 전에 밥을 챙겨줄 수 있는 고양이의 최대 마릿수를 출력한다.

예제2

예제 1
입력
```
5 6
6
0 0
1 6
2 2
2 1
4 3
5 6
```
예상 출력
```
5
```
예제 2
입력
```
100 100
3
101 101
102 100
100 100
```
예상 출력
```
1
```