银狐与怪物

题目描述

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

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

银狐可以使用炸弹攻击怪物。 在坐标 $x$ 使用炸弹时,可以降低坐标在 $x-D$ 以上 $x+D$ 以下范围内的所有怪物的 $A$ 点体力。 除了炸弹之外,没有其他方法可以减少怪物的体力。

当所有怪物的体力都降到 $0$ 以下(含)时,银狐获胜。

求银狐击败怪物所需使用炸弹的次数的最小值。

输入格式

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

$N$ $D$ $A$
$X_1$ $H_1$
: $X_N$ $H_N$

输出格式

输出银狐击败怪物所需使用炸弹的次数的最小值。

样例

3 3 2
1 2
5 4
9 2

2

首先在坐标 $4$ 使用炸弹,可以降低第 $1$ 只和第 $2$ 只怪物的 $2$ 点体力。

接着在坐标 $6$ 使用炸弹,可以降低第 $2$ 只和第 $3$ 只怪物的 $2$ 点体力。

这 $2$ 次就把所有怪物的体力降到了 $0$。只用 $1$ 次无法把所有怪物的体力降到 $0$ 以下。

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

5

在坐标 $5$ 使用炸弹 $5$ 次。

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

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