Fusnote
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.
InputThe 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.
OutputThe first and only line of output should contain the minimal number of pages a book can have.
Input
Output
5 5
1
3 2 Output
2Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.