시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 17 | 9 | 8 | 50.000% |
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.
5 5 1 3 2
2
7 3 2 2 1 4 2
4
10 5 5 3 3 4 1 6 2 6 1 9 3
6