← 返回题目列表

AtCoder · awc0009_b

B. 地牢探索

中文机器翻译题面 查看原题

分数: 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