Tower Defense
题意翻译
### 题意简述
一个塔防游戏。
一共有 $n$ 个塔按 $1 \sim n$ 的顺序排成一列,每座塔都有魔力容量 $c_i$ 和魔力恢复速率 $r_i$。对于一座塔 $i$,每过一秒它的魔力 $m_i$ 会变为 $\min(m_i+r_i, c_i)$。每座塔初始时满魔力。
一共有 $q$ 个怪物,每个怪物有两个属性 $t_i$ 和 $h_i$,表示这个怪物会在第 $t_i$ 秒出现在第一座塔前面。当它到一座塔 $j$ 面前时,自己的血量 $h_i$ 会减少 $\min(h_i,m_j)$,塔的魔力也会减少这个数。当怪物血量 $h_i=0$ 时停止移动,否则它下一秒会移动到下一座塔。
有些怪物在经过塔 $n$ 后血量仍未减少至 $0$,请你求出这样的怪物最终剩下的血量总和。
### 数据范围
- $1\le n,q\le2\times10^5$
- $1\le c_i,r_i\le 10^9$
- $1\le h_i\le10^{12}$
- $0\le t_i\le 2\times10^5$
- $\forall 1\le j<q,t_j<t_{j+1}$
题目描述
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.
输入输出样例
输入样例 #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