#P1651F. Tower Defense

    ID: 69 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbrute forcedata structures*3000

Tower Defense

Description

Monocarp is playing a tower defense game. A level in the game can be represented as an OX axis, where each lattice point from 11 to nn contains a tower in it.

The tower in the ii-th point has cic_i mana capacity and rir_i mana regeneration rate. In the beginning, before the 00-th second, each tower has full mana. If, at the end of some second, the ii-th tower has xx mana, then it becomes min(x+ri,ci)\mathit{min}(x + r_i, c_i) mana for the next second.

There are qq monsters spawning on a level. The jj-th monster spawns at point 11 at the beginning of tjt_j-th second, and it has hjh_j health. Every monster is moving 11 point per second in the direction of increasing coordinate.

When a monster passes the tower, the tower deals min(H,M)\mathit{min}(H, M) damage to it, where HH is the current health of the monster and MM is the current mana amount of the tower. This amount gets subtracted from both monster's health and tower's mana.

Unfortunately, sometimes some monsters can pass all nn towers and remain alive. Monocarp wants to know what will be the total health of the monsters after they pass all towers.

The first line contains a single integer nn (1n21051 \le n \le 2 \cdot 10^5) — the number of towers.

The ii-th of the next nn lines contains two integers cic_i and rir_i (1rici1091 \le r_i \le c_i \le 10^9) — the mana capacity and the mana regeneration rate of the ii-th tower.

The next line contains a single integer qq (1q21051 \le q \le 2 \cdot 10^5) — the number of monsters.

The jj-th of the next qq lines contains two integers tjt_j and hjh_j (0tj21050 \le t_j \le 2 \cdot 10^5; 1hj10121 \le h_j \le 10^{12}) — the time the jj-th monster spawns and its health.

The monsters are listed in the increasing order of their spawn time, so tj<tj+1t_j < t_{j+1} for all 1jq11 \le j \le q-1.

Print a single integer — the total health of all monsters after they pass all towers.

Input

The first line contains a single integer nn (1n21051 \le n \le 2 \cdot 10^5) — the number of towers.

The ii-th of the next nn lines contains two integers cic_i and rir_i (1rici1091 \le r_i \le c_i \le 10^9) — the mana capacity and the mana regeneration rate of the ii-th tower.

The next line contains a single integer qq (1q21051 \le q \le 2 \cdot 10^5) — the number of monsters.

The jj-th of the next qq lines contains two integers tjt_j and hjh_j (0tj21050 \le t_j \le 2 \cdot 10^5; 1hj10121 \le h_j \le 10^{12}) — the time the jj-th monster spawns and its health.

The monsters are listed in the increasing order of their spawn time, so tj<tj+1t_j < t_{j+1} for all 1jq11 \le j \le q-1.

Output

Print a single integer — the total health of all monsters after they pass all towers.

Samples

样例输入 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