B. Шаги
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Однажды Вася вышел во двор погулять, а там не оказалось его друзей, с которыми он обычно играл в салки. Мальчик не растерялся и решил поиграть в салки сам с собой. «Как он это сделал?» — спросите вы. Очень просто.

Вася заметил, что двор представляет собой прямоугольное поле размером n × m клеток, а каждая клетка имеет координаты (x, y) (1 ≤ x ≤ n, 1 ≤ y ≤ m), где x — номер строки поля, y — номер столбца поля.

Изначально, Вася стоит в клетке с координатами (xc, yc). Для игры у него заготовлен список из k векторов (dxi, dyi) ненулевой длины. Действие игры происходит следующим образом. Мальчик рассматривает все вектора в порядке от 1 до k, и по очереди выбирает каждый из них в качестве текущего. Выбрав вектор в качестве текущего, мальчик делает максимально возможное количество корректных шагов по направлению этого вектора (возможно, ноль шагов).

Шагом называется одно перемещение из клетки, где сейчас стоит мальчик, в направлении текущего вектора. То есть, если Вася находится в клетке (x, y), а текущий вектор — (dx, dy), то за один шаг Вася перемещается в клетку (x + dx, y + dy). Шаг считается корректным, если, совершая этот шаг, мальчик не выходит за пределы двора.

Вася шагал и шагал, шагал и шагал, до тех пор, пока вектора из его списка не закончились. Он так много шагал, что совершенно позабыл, сколько шагов он сделал. Помогите мальчику — посчитайте, сколько шагов он сделал.

Входные данные

В первой строке входных данных даны два целых числа n и m (1 ≤ n, m ≤ 109) — размеры двора. Во второй строке записаны целые числа xc и yc — координаты начальной клетки (1 ≤ xc ≤ n, 1 ≤ yc ≤ m).

В третьей строке задано целое число k (1 ≤ k ≤ 104) — количество векторов. Далее идут k строк, в каждой из которых записаны два целых числа dxi и dyi (|dxi|, |dyi| ≤ 109, |dx| + |dy| ≥ 1).

Выходные данные

Выведите единственное целое число — количество шагов, которые сделал Вася.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4 5
1 1
3
1 1
1 1
0 -2
Выходные данные
4
Входные данные
10 10
1 2
1
-1 0
Выходные данные
0
Примечание

В первом примере Вася изначально находится в клетке (1, 1) и делает 3 шага по первому вектору (1, 1) последовательно посещая клетки: (2, 2), (3, 3), (4, 4). Затем он делает 0 шагов по второму вектору (1, 1). И 1 шаг по третьему вектору (0,  - 2) и оказывается в клетке (4, 2). В итоге Вася сделает 4 шага.

Во втором примере Вася изначально находится в клетке (1, 2) и делает 0 шагов по вектору ( - 1, 0), так как клетка с координатами (0, 2) находится вне двора.