Footnotes

Time limit1sMemory limit128 MB

Summary

Given text lines and footnotes attached to specific lines, compute the minimum number of pages so that each page holds consecutive text lines plus their footnotes within a line limit K.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Prefix sum
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
5 5
1
3 2
```
Expected output
```
2
```
Example 2
Input
```
7 3
2
2 1
4 2
```
Expected output
```
4
```
Example 3
Input
```
10 5
5
3 3
4 1
6 2
6 1
9 3
```
Expected output
```
6
```