Monocarp 正在玩塔防游戏。游戏中的关卡可以表示为一条 OX 轴,其中从 $$$1$$$ 到 $$$n$$$ 的每个格点都包含一座塔。
第$$$i$$$点的塔具有$$$c_i$$$法力容量和$$$r_i$$$法力再生率。一开始,在第 $$$0$$$ 秒之前,每座塔都有满法力。如果在某一秒结束时,第 $$$i$$$ 塔拥有 $$$x$$$ 法力,那么下一秒它就变成 $$$\mathit{min}(x + r_i, c_i)$$$ 法力。
某个关卡上生成了 $$$q$$$ 怪物。第 $$$j$$$ 个怪物在第 $$$t_j$$$ 秒开始时的 $$$1$$$ 点生成,并且具有 $$$h_j$$$ 生命值。每个怪物每秒沿坐标增加的方向移动 $$$1$$$ 点。
当怪物经过塔时,塔对其造成 $$$\mathit{min}(H, M)$$$ 伤害,其中 $$$H$$$ 是怪物当前的生命值,$$$M$$$ 是塔当前的法力值。该数量将从怪物的生命值和塔的法力值中减去。
不幸的是,有时有些怪物可以通过所有 $$$n$$$ 塔并保持活力。 Monocarp 想知道怪物通过所有塔后的总生命值是多少。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 塔的数量。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$c_i$$$ 和 $$$r_i$$$ ($$$1 \le r_i \le c_i \le 10^9$$$) — 第 $$$i$$$ 塔的法力容量和法力再生率。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 怪物的数量。
接下来的 $$$q$$$ 行的第 $$$j$$$ 包含两个整数 $$$t_j$$$ 和 $$$h_j$$$ ($$$0 \le t_j \le 2 \cdot 10^5$$$; $$$1 \le h_j \le 10^{12}$$$) — 时间$$$j$$$ 个怪物的生成及其生命值。
怪物按其生成时间的升序排列,因此对于所有 $$$1 \le j \le q-1$$$,$$$t_j < t_{j+1}$$$。
输出
打印一个整数——所有怪物通过所有塔后的总生命值。
示例
输入 #1
3 5 1 7 4 4 2 4 0 14 1 10 3 16 10 16
输出 #1
4
输入 #2
5 2 1 4 1 5 4 7 5 8 3 9 1 21 2 18 3 14 4 24 5 8 6 25 7 19 8 24 9 24
输出 #2
40