Республиканская олимпиада по информатике 2008 год

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Рабочим надо оклеить обоями одну стену шириной $X$ и высотой $Y$. Рулон обоев представляет собой прямоугольник шириной A и высотой B сантиметров, разделенный на B горизонтальных полосок одинаковой высоты. Полоски раскрашены в K цветов следующим образом (полоски нумеруются снизу вверх):
полоски номер 1, K + 1, 2K + 1, ... в цвет номер 1;
полоски номер 2, K + 2, 2K + 2, ... в цвет номер 2;
...
полоски номер K, 2K, 3K, ... в цвет номер K.
Стена должна быть обклеена так, чтобы цвета соседних по горизонтали полосок совпадали, а вертикально чередовались так же, как и в рулоне (однако цвет нижней полоски может быть любым). После оклеивания предыдущих стен осталось $N$ обрезков. Ширина каждого из обрезков равна ширине рулона. Какое минимальное количество целых рулонов надо докупить, чтобы оклеить стену полностью. Покупать часть рулона нельзя. Обои можно разрезать по границам полосок.

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

Первая строка входного файла содержит шесть целых положительных чисел $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