Республиканская олимпиада по информатике 2008 года за 11 класс | Казахстанские олимпиады

Задача D. Обои

Рабочим надо оклеить обоями одну стену шириной $X$ и высотой $Y$. Рулон обоев представляет собой прямоугольник шириной A и высотой B сантиметров, разделенный на B горизонтальных полосок одинаковой высоты. Полоски раскрашены в K цветов следующим образом (полоски нумеруются снизу вверх):

Формат входного файла

Первая строка входного файла содержит шесть целых положительных чисел $X$, $Y$, $A$, $B$, $K$, $N$ (1 <= $X, Y, A, B$ <= $10^9$, 1 <= $K, N$ <= $5 * 10^5$, $X mod A = 0$, $B mod K = 0$). Следующие $N$ строк содержат по два целых числа — номер цвета нижней полоски обрезка и высоту обрезка в сантиметрах. Гарантируется, что каждый обрезок — часть целого рулона. Числа в строках разделены пробелами.

Формат выходного файла

Выходной файл должен содержать одно целое число — минимальное количество докупаемых рулонов.

Примеры

Вход

5 5 1 10 10 10
6 4
6 2
3 3
2 4
10 1
5 2
6 2
8 3
2 5
2 5

Выход

2