시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 128 MB42133.333%

문제

A text in a book consists of a sequence of lines. A line may contain references to footnotes. A footnote consists of one or more lines and it have to be printed together with its reference on the same page. Once a footnote is printed on a page, only another footnote may follow it on that page. A maximal number of lines that can be printed on one page is known. No page of a book may contain more than that number of lines, including footnotes.

Write a program that will compute the minimal number of pages a book can have.

입력

The first line of input contains two integers: N, a number of lines in a document (2 ≤ N ≤ 1000), and K, maximal number of lines a page of a book may contain (2 ≤ K ≤ 1000), separated by a space character.

The second line of input contains an integer F, 1 ≤ F ≤ 100, a number of footnotes in a book.

Each of the next F lines consists of two numbers, X and Y, separated by a space character, meaning that X-th line of the text has a reference to a footnote consisting of Y lines. Those footnotes descriptions will be sorted with respect to the lines where they are being referenced.

Note: Input data will be chosen so that a solution always exists.

출력

The first and only line of output should contain the minimal number of pages a book can have.

예제 입력 1

5 5
1
3 2

예제 출력 1

2

예제 입력 2

7 3
2
2 1
4 2

예제 출력 2

4

예제 입력 3

10 5
5
3 3
4 1
6 2
6 1
9 3

예제 출력 3

6