A14906 | Tower Defense

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

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

There are $q$ monsters spawning on a level. The $j$ -th monster spawns at point $1$ at the beginning of $t_j$ -th second, and it has $h_j$ health. Every monster is moving $1$ point per second in the direction of increasing coordinate.

When a monster passes the tower, the tower deals $\mathit{min}(H, M)$ damage to it, where $H$ is the current health of the monster and $M$ 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 $n$ 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 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of towers.

The $i$ -th of the next $n$ lines contains two integers $c_i$ and $r_i$ ( $1 \le r_i \le c_i \le 10^9$ ) — the mana capacity and the mana regeneration rate of the $i$ -th tower.

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

The $j$ -th of the next $q$ lines contains two integers $t_j$ and $h_j$ ( $0 \le t_j \le 2 \cdot 10^5$ ; $1 \le h_j \le 10^{12}$ ) — the time the $j$ -th monster spawns and its health.

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

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