← 返回题目列表

AtCoder · abc153_f

F. 银狐 vs 怪物

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

分数: 600 点

问题陈述

银狐正在与 N 怪物。

怪物站成一排,我们可以假设它们站在一条数轴上。的 i- 第一个怪物,站在坐标处 X_i,有 健康 of H_i.

银狐可以使用炸弹攻击怪物。 在坐标处使用炸弹 x 降低坐标之间所有怪物的生命值 x-D 和 x+D (含)由 A。 除了炸弹之外没有其他方法可以降低怪物的生命值。

当所有怪物的生命值变为时,银狐获胜 0 或以下。

求获胜所需的最少炸弹数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq D \leq 10^9
  • 1 \leq A \leq 10^9
  • 0 \leq X_i \leq 10^9
  • 1 \leq H_i \leq 10^9
  • X_i 是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N D A
X_1 H_1
:
X_N H_N

输出

打印获胜所需的最少炸弹数量。


示例输入 1

3 3 2
1 2
5 4
9 2

示例输出 1

2

首先,我们在坐标处使用炸弹 4 使第一个和第二个怪物的生命值减少 2.

然后,在坐标处使用炸弹 6 减少第二个和第三个怪物的生命值 2.

现在,所有怪物的生命值都是 0。 我们无法让所有怪物的生命值都下降到 0 或以下,只需一枚炸弹。


示例输入 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

示例输出 2

5

我们应该在坐标处使用五枚炸弹 5.


示例输入 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

示例输出 3

3000000000

注意溢出。