← 返回题目列表

Codeforces · 152/B

B. 步骤

中文机器翻译题面 查看原题

有一天,Vasya 出去在院子里散步,但外面没有他的朋友,也没有人可以和他玩碰碰跑。但男孩并没有失去斗志,决定和自己玩碰触、奔跑。你可能会问:“他是怎么做到的?”答案很简单。

Vasya 注意到院子是一个 n × m 的矩形场地。这些正方形的坐标为 (x, y) (1 ≤ x ≤ n, 1 ≤ y ≤ m),其中 x 是行索引,y 是列索引。

最初 Vasya 站在坐标为 (xc, yc) 的正方形中。为了进行游戏,他获得了一个包含 k 个非零长度向量 (dxi, dyi) 的列表。游戏是这样进行的。男孩按照从 1 到 k 的顺序考虑所有向量,并连续选择每个向量作为当前向量。男孩选择当前向量后,他会在向量的方向上迈出最大可能的有效步数(有可能他迈出零步)。

一步被定义为从男孩现在站立的正方形开始,沿当前矢量的方向移动一次。也就是说,如果 Vasya 位于方格 (x, y) 中,并且当前向量为 (dx, dy),则一步将 Vasya 移动到方格 (x + dx, y + dy)。如果男孩执行该步骤后没有走出院子,则该步骤被视为有效。

Vasya 一直踩啊,踩啊,直到列表中的矢量用完。哈走了太久,他完全忘记了自己走了多少步。帮助男孩并数一下他走了多少步。

输入

第一输入行包含两个整数 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)。

输出

打印单个数字——Vasya 已走了的步数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

4 5
1 1
3
1 1
1 1
0 -2

输出 #1

4

输入 #2

10 10
1 2
1
-1 0

输出 #2

0

注意

在第一个示例中,Vasya 最初位于正方形 (1, 1) 处,并按照第一个向量 (1, 1) 走了 3 步。于是,他连续访问了方格(2, 2), (3, 3), (4, 4)。然后他按照第二个向量 (1, 1) 走了 0 步。他又向第三个向量 (0, - 2) 迈出 1 步,最终到达正方形 (4, 2)。瓦西亚总共走了 4 步。

在第二个示例中,Vasya 最初位于方格 (1, 2) 中,并通过向量 (- 1, 0) 移动 0 步,因为坐标为 (0, 2) 的方格位于院子外。