[Solution] Tower Defense solution codeforces

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 11 to 𝑛n contains a tower in it.

The tower in the 𝑖i-th point has 𝑐𝑖ci mana capacity and 𝑟𝑖ri mana regeneration rate. In the beginning, before the 00-th second, each tower has full mana. If, at the end of some second, the 𝑖i-th tower has 𝑥x mana, then it becomes min(𝑥+𝑟𝑖,𝑐𝑖)min(x+ri,ci) mana for the next second.

Tower Defense solution codeforces

There are 𝑞q monsters spawning on a level. The 𝑗j-th monster spawns at point 11 at the beginning of 𝑡𝑗tj-th second, and it has 𝑗hj 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(𝐻,𝑀)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.

Input

The first line contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105) — the number of towers.

The 𝑖i-th of the next 𝑛n lines contains two integers 𝑐𝑖ci and 𝑟𝑖ri (1𝑟𝑖𝑐𝑖1091≤ri≤ci≤109) — the mana capacity and the mana regeneration rate of the 𝑖i-th tower.

The next line contains a single integer 𝑞q (1𝑞21051≤q≤2⋅105) — the number of monsters.

Tower Defense solution codeforces

The 𝑗j-th of the next 𝑞q lines contains two integers 𝑡𝑗tj and 𝑗hj (0𝑡𝑗21050≤tj≤2⋅1051𝑗10121≤hj≤1012) — the time the 𝑗j-th monster spawns and its health.

The monsters are listed in the increasing order of their spawn time, so 𝑡𝑗<𝑡𝑗+1tj<tj+1 for all 1𝑗𝑞11≤j≤q−1.

Output

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

Examples

input

Copy
3
5 1
7 4
4 2
4
0 14
1 10
3 16
10 16

Tower Defense solution codeforces

4

input

Copy
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

output

Copy
40

 

Leave a Comment