Footnotes

The text of a book consists of several lines. A text line may contain references to footnotes. Each footnote consists of one or more lines and must be printed on the same page as the text line that references it.

Once footnotes begin on a page, only other footnotes may follow them on that page; no more text lines can appear after them. Therefore, a page contains some consecutive text lines together with all footnotes referenced by those lines.

You are given K, the maximum number of lines that can be printed on one page. Counting both text lines and footnote lines, no page may contain more than K lines.

Find the minimum number of pages needed to print the book.

The first line contains two integers N and K: the number of text lines and the maximum number of lines that may be printed on one page. (2 <= N <= 1000, 2 <= K <= 1000)

The second line contains the number of footnotes F. (1 <= F <= 100)

Each of the next F lines contains two integers X and Y. This means that the X-th text line references a footnote of Y lines. Multiple footnotes may be referenced by the same text line, and the footnotes are given in nondecreasing order of the text line that references them.

The input is always chosen so that the book can be printed.

Print the minimum number of pages needed to print the book.