F - 银狐对怪物

得分 : $600$ 分

题目描述

银狐正在与 $N$ 个怪物战斗。

怪物们站成了一排，我们可以将它们看作站在数轴上。第 $i$ 个怪物位于坐标 $X_i$ 处，其拥有 $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$

输出

输出获胜所需要的最小炸弹数量。

3 3 2
1 2
5 4
9 2

2

首先，让我们在坐标 $4$ 处使用炸弹，将第一个和第二个怪物的生命值减少 $2$。

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

现在，所有怪物的生命值均为 $0$。 使用一颗炸弹无法使所有怪物的生命值降至 $0$ 或以下。

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

5

我们应该在坐标 $5$ 处使用五颗炸弹。

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

3000000000

注意避免溢出。