有一天,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) 的方格位于院子外。