[ABC153F] Silver Fox vs Monster
题意翻译
$Silver\ Fox$ 在打怪。他的面前有 $N$ 只怪。
这 $N$ 只怪站在一行上。为了方便,我们把他们看作在一个数轴上。其中第 $i$ 只怪物的坐标为 $X_i$ ,有 $H_i$ 点血量。
他可以用炸弹来攻击这些怪物。如果选择在位置 $x$ 投放炸弹,那么坐标位于 $x-D$ 和 $x+D$ 之间的怪物会全部减少 $A$ 点血量。
如果所有怪物的血量都 $\le 0$,那么他就获胜了。
找到在获胜的情况下,$Silver\ Fox$ 需要投放的炸弹最少有多少个。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc153/tasks/abc153_f
ギンギツネは $ N $ 体のモンスターと戦っています。
モンスターは $ 1 $ 列に並んでおり、数直線上にいるとみなすことができます。$ i $ 番目のモンスターは座標 $ X_i $ にいて、体力は $ H_i $ です。
ギンギツネは爆弾を使ってモンスターを攻撃することができます。 座標 $ x $ で爆弾を使うと、座標が $ x-D $ 以上 $ x+D $ 以下の範囲にいる全てのモンスターの体力を $ A $ 減らすことができます。 爆弾を使う以外の方法でモンスターの体力を減らすことはできません。
全てのモンスターの体力を $ 0 $ 以下にすればギンギツネの勝ちです。
ギンギツネがモンスターに勝つまでに爆弾を使う回数の最小値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ D $ $ A $ $ X_1 $ $ H_1 $ : $ X_N $ $ H_N $
输出格式
ギンギツネがモンスターに勝つまでに爆弾を使う回数の最小値を出力せよ。
输入输出样例
输入样例 #1
3 3 2
1 2
5 4
9 2
输出样例 #1
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 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 $ は相異なる。
- 入力中のすべての値は整数である。
### Sample Explanation 1
最初に座標 $ 4 $ で爆弾を使うことで、$ 1 $ 番目と $ 2 $ 番目のモンスターの体力を $ 2 $ 減らせます。 次に座標 $ 6 $ で爆弾を使うことで、$ 2 $ 番目と $ 3 $ 番目のモンスターの体力を $ 2 $ 減らせます。 この $ 2 $ 回で全てのモンスターの体力を $ 0 $ にできました。$ 1 $ 回で全てのモンスターの体力を $ 0 $ 以下にすることはできません。
### Sample Explanation 2
座標 $ 5 $ で爆弾を $ 5 $ 回使います。
### Sample Explanation 3
オーバーフローに注意してください。