carte

A book's text has N lines, numbered from 1 to N.
A line may contain one or more references to footnotes. A footnote is represented by one or more lines and must appear on the same page as the line containing the reference to that footnote. Footnotes appear in the lower part of the page and only another footnote may appear below a footnote on the same page.
The maximum number of lines (text and footnotes) that can be written on the same page is known.

Task

Write a program that determines the minimum number of pages the book can have.

Input Data

Input file carte.in contains on the first line two positive integers, N and K, separated by a space (N represents the number of lines in the book and K represents the maximum number of lines that can be written on a page). The second line contains a positive integer F, representing the number of footnotes in the book. Each of the next F lines contains two positive integers, X Y, separated by a space, with the meaning that on the Xth line of text in the book there is a reference to a footnote comprised of Y lines. Footnotes are specified in the line order they are referred to.

Output Data

Output file carte.out will contain a single line with the minimum number of pages the book has.

Constraints and Statements

Example
carte.in carte.out carte.in carte.out carte.in carte.out
5 5
1
3 2

2

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

6

Explanations (a solution to obtain the minimum number of pages specified in each example):
In example one, page one contains text lines 1, 2, 3 and the footnote referenced on line 3, and page two contains text lines 4 and 5.
In example two, page one contains text lines 1 and 2, as well as the footnote referenced on line 3. Page two contains line 3, page three contains line 4 and the footnote referenced on line 4, and page four contains lines 5, 6, 7.
In example three,page one contains text lines 1 and 2. Page two contains text line 3 and the footnote referenced on line 3. Page three contains lines 4 and 5, as well as the footnote referenced on line 4. Page four contains lines 6 and 7, as well as the two footnotes referenced on line 6. Page five contains lines 8 and 9, as well as the footnote referenced on line 9. And page six contains line 10.

Time limit: 0.1 seconds/test

prof. Marinel Serban
"Grigore Moisil" Iaşi IT High School
 Contact:marinel_serban@yahoo.com