#P1651F. Tower Defense
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 to contains a tower in it.
The tower in the -th point has mana capacity and mana regeneration rate. In the beginning, before the -th second, each tower has full mana. If, at the end of some second, the -th tower has mana, then it becomes mana for the next second.
There are monsters spawning on a level. The -th monster spawns at point at the beginning of -th second, and it has health. Every monster is moving point per second in the direction of increasing coordinate.
When a monster passes the tower, the tower deals damage to it, where is the current health of the monster and 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 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 () — the number of towers.
The -th of the next lines contains two integers and () — the mana capacity and the mana regeneration rate of the -th tower.
The next line contains a single integer () — the number of monsters.
The -th of the next lines contains two integers and (; ) — the time the -th monster spawns and its health.
The monsters are listed in the increasing order of their spawn time, so for all .
Print a single integer — the total health of all monsters after they pass all towers.
Input
The first line contains a single integer () — the number of towers.
The -th of the next lines contains two integers and () — the mana capacity and the mana regeneration rate of the -th tower.
The next line contains a single integer () — the number of monsters.
The -th of the next lines contains two integers and (; ) — the time the -th monster spawns and its health.
The monsters are listed in the increasing order of their spawn time, so for all .
Output
Print a single integer — the total health of all monsters after they pass all towers.