Tower Defense solution codeforces – 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 $m i n (x + r_{i}, c_{i})$ mana for the next second.

Tower Defense solution codeforces

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 $m i n (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.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 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 \leq r_{i} \leq c_{i} \leq 10^{9}$ ) — the mana capacity and the mana regeneration rate of the $i$ -th tower.

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