AT_abc153_f [ABC153F] Silver Fox vs Monster

题目描述

银狐正在与 $N$ 只怪兽战斗。

怪兽们排成一列，可以认为它们位于数轴上。第 $i$ 只怪兽位于坐标 $X_i$，体力为 $H_i$。

银狐可以使用炸弹攻击怪兽。在坐标 $x$ 处使用炸弹时，所有位于 $x-D$ 以上且 $x+D$ 以下范围内的怪兽的体力都会减少 $A$。除了使用炸弹，无法以其他方式减少怪兽的体力。

如果所有怪兽的体力都降为 $0$ 或以下，则银狐获胜。

请你求出银狐获胜所需使用炸弹的最小次数。

输入格式

输入以如下格式从标准输入读入。

$N$ $D$ $A$
$X_1$ $H_1$
$X_2$ $H_2$
$\vdots$
$X_N$ $H_N$

输出格式

输出银狐获胜所需使用炸弹的最小次数。

输入输出样例 #1

输入 #1

3 3 2
1 2
5 4
9 2

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

5

输入输出样例 #3

输入 #3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

输出 #3

3000000000

说明/提示

限制条件

• $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$ 互不相同。
• 输入中的所有数值均为整数。

样例解释 1

首先在坐标 $4$ 处使用炸弹，可以使第 $1$ 只和第 $2$ 只怪兽的体力各减少 $2$。接着在坐标 $6$ 处使用炸弹，可以使第 $2$ 只和第 $3$ 只怪兽的体力各减少 $2$。通过这 $2$ 次操作，所有怪兽的体力都降为 $0$。无法通过 $1$ 次操作使所有怪兽的体力降为 $0$ 或以下。

样例解释 2

在坐标 $5$ 处连续使用 $5$ 次炸弹。

样例解释 3

请注意不要发生溢出。

由 ChatGPT 4.1 翻译