分数: 266 分
问题陈述
高桥挑战自己探索地牢。
地牢里有 N 房间排列成一排。的 i左边第一个房间包含 1 怪物。的 i第-个怪物有力量 H_i,被击败后,它会掉落一个可以恢复的物品 P_i 健康点。
高桥从房间访问所有房间一次 1 到房间 N 按房间号递增的顺序。高桥的初始健康状况是 S。健康没有上限。
参观每个房间时 i,将自动应用以下规则。高桥在这件事上别无选择。
- 如果他当前的健康状况是 大于或等于 H_i,高桥击败了怪物。首先,他的健康状况下降 H_i,之后立即恢复 P_i。也就是说,健康的净变化是 -H_i + P_i。因为他的健康状况至少是 H_i 战斗前,保证战斗结束后生命值非负 H_i 减少。
- 如果他当前的健康状况是 小于 H_i,高桥无法击败怪物并穿过房间。在这种情况下,他的健康状况不会改变。
对于每个没有击败怪物的房间,高桥必须支付 C.
访问完所有 N 房间,确定高桥必须支付的总罚款。也就是说,如果怪物没有被击败的房间数是 k,输出 k \times C.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq S \leq 10^9
- 1 \leq C \leq 10^9
- 1 \leq H_i \leq 10^9
- 0 \leq P_i \leq 10^9
- 所有输入值均为整数。
输入
N S C H_1 P_1 H_2 P_2 \vdots H_N P_N
- 第一行包含 N 代表房间数量, S 代表高桥的初始健康状况,以及 C 代表每个房间的罚金,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个房间的信息 N 行。
- 的 (1 + i)第行包含强度 H_i 的 i第个怪物和生命恢复量 P_i 击败该怪物后,以空格分隔。
输出
在一行中输出高桥必须支付的总罚款。
示例输入 1
3 10 5 3 1 12 5 5 3
示例输出 1
5
示例输入 2
5 7 100 5 2 3 10 20 5 11 0 1 0
示例输出 2
200
示例输入 3
8 15 1000000000 10 8 5 3 20 0 8 7 10 10 100 50 1 0 9 5
示例输出 3
2000000000