分数: 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
注意溢出。