#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005


int N;
ll max_HP,HP;
ll damage[SIZE],sum_damage[SIZE],recovery[SIZE];

int main(){

	scanf("%d %lld",&N,&max_HP);

	sum_damage[0] = 0;

	for(int i = 0; i < N-1; i++){

		scanf("%lld %lld",&damage[i],&recovery[i]);

		if(damage[i] >= max_HP){

			printf("-1\n");
			return 0;
		}

		sum_damage[i+1] = sum_damage[i]+damage[i]; //累積和にする
	}

	deque<int> DEQ;

	ll ans = 0;
	HP = max_HP;

	for(int i = 0; i <= N-2; i++){

		/*過去に、【とある階で回復していた】ことに【変更】する場合、【既に食らったダメージ】を再び被ることはないので、
		 * ■■■無駄(=上限による回復の打ち切り)が発生しない限り■■■、回復量が大きい泉で回復していたことにするのが良いはず。
		 * HPの折れ線グラフを、より少ない回数で、必要な分だけ上にシフトさせるということ★*/

		while(DEQ.empty() == false && recovery[DEQ.back()] <= recovery[i]){

			DEQ.pop_back(); //回数の最小化を図っているので、階iの回復量以下の泉は不要。過去使っていたことにすると損になるため
		}
		DEQ.push_back(i); //この階の泉

		while(DEQ.empty() == false && sum_damage[i]-sum_damage[DEQ.front()] >= max_HP){
			/*最大HP以上に、移動の間に体力を失うならば、もうその泉は忘れて良い
			 * →仮にその泉で完全回復したとしても、現在の体力が増えないため*/

			DEQ.pop_front();
		}

		if(HP <= damage[i]){ //何もしなければ死ぬ場合

			for(int k = 0; k < DEQ.size(); k++){

				ll theory_max = max_HP-(sum_damage[i]-sum_damage[DEQ[k]]); //階DEQ[k]で完全回復した場合に、今のHPがいくらになっているか

				if(theory_max <= HP){
					/*
					 * 仮に階DEQ[k]で完全回復したとしても現在のHPは増えないのでSKIP
					 * */
					continue;
				}

				ll need_HP = damage[i]+1; //死なないために必要な最少の体力

				ll limit = min(theory_max,need_HP)-HP; //今回の回復量の上限:回数の最小化を図るため

				/*DEQには回復量の降順にデータが入っており、かつ【過去の行動を変えたとしても、現在までに食らったダメージは変化しないため】
				 * 【無駄が生じない限り】は、選択肢の中で最大の回復量を誇る階DEQ[k]で回復するのが最適なはず。
				 * 上限の存在による【無駄】が発生した場合は、DEQ[k+1]で回復した方が
				 * 現在のHPが高くなる可能性があるので、残りの【回復し切らなかった分(limitの残り)】について
				 * 再帰的に調べる必要がある
				 * HPの折れ線グラフは、無駄(上限による回復の打ち切り)を生じさせなかった場合、
				 * 階DEQ[k]においてのHPは、ぴったりmax_HP,またはそれ未満になるはずであり、
				 * その位置までグラフをシフトさせるための必要回数は、回復量が選択肢の中で最大であるが故に、
				 * 最も効率が良いはず
				 * */

				int count = limit/recovery[DEQ[k]];
				HP += recovery[DEQ[k]]*count; //★★★確定回復量★★★
				ans += count;

				if(limit%recovery[DEQ[k]] == 0){ //階DEQ[k]で無駄が生じなかった場合

					if(HP == need_HP){ //十分回復

						break;

					}else{ //need_HPでないということはHP==theroy_maxであるはずなので、次の泉を見に行く

						continue;
					}
				}

				//階DEQ[k]で無駄が生じた場合(回復しきらなかった分がある場合)

				if(k+1 == DEQ.size()){ //もう泉が残っていない場合→階iの泉→最後の一回もこの階で回復

					HP = min(HP+recovery[DEQ[k]],max_HP);
					ans++;

				}else{ //最後の1回を、DEQ[k]での回復に使うべきか、DEQ[k+1]での回復に使うべきかを【再帰的に】検討する

					/*最後の1回を、階DEQ[k]での回復に充てる場合*/
					ll past_HP = HP+(sum_damage[i]-sum_damage[DEQ[k]]); //階DEQ[k]でHPがいくつだったか【回復しきらなかった分があるため、max_HPではあり得ない】
					past_HP = min(past_HP+recovery[DEQ[k]],max_HP); //あと1回、階DEQ[k]で回復した場合の、階DEQ[k]でのHP
					ll tmp_HP = past_HP-(sum_damage[i]-sum_damage[DEQ[k]]); //この場合、現在(階i)のHPはいくつになるか


					/*最後の1回を、階DEQ[k+1]での回復に充てる場合*/
					ll past_HP_next = HP+(sum_damage[i]-sum_damage[DEQ[k+1]]); //次の階でのHPがいくつあったか
					past_HP_next = min(past_HP_next+recovery[DEQ[k+1]],max_HP);

					ll tmp_HP_next = past_HP_next-(sum_damage[i]-sum_damage[DEQ[k+1]]); //階DEQ[k+1]で回復していたとしたら、現在のHPはいくつか

					if(tmp_HP >= tmp_HP_next){ //階DEQ[k]を採用した方が現在のHPが高くなる場合、または同じである場合

						ans++; //階DEQ[k]でもう1回回復
						HP = tmp_HP;

					}else{

						continue; //判断を保留【再帰的に論理が伝播するため】
					}
				}

				if(HP >= need_HP)break;
			}
		}

		HP -= damage[i];

		if(HP <= 0){
			printf("-1\n");
			return 0;
		}
	}

	printf("%lld\n",ans);

	return 0;
}


### Prompt

Construct a cpp code solution to the problem outlined:

problem

You want to get a treasure on the Nth basement floor of a dungeon. First, you are on the 1st basement floor and your health is H (H is a positive integer). Go downstairs. Sometimes physical strength is consumed. The physical strength consumed when descending to the lower floor on each floor is known in advance. On the other hand, there is one recovery fountain on each floor, and you can recover with each use of the fountain. Each has its own health. You will die if your health drops below 0. Also, your health will never be higher than H. You can use the Recovery Fountain as many times as you like, but it will take time to recover. Because of this, you want to use the fountain as few times as possible.

N, H, when given the health consumed when descending downstairs on each floor, and the health to recover when using the recovery fountain once on each floor, underground N without reducing health to 0 or less. Create a program to find the minimum number of times the fountain has been used to reach the floor.

Also, once you go downstairs, you can't go upstairs until you get the treasure.



input

The input consists of N lines. The first line of the input contains two integers N, H (2 ≤ N ≤ 100000 = 105, 1 ≤ H ≤ 10000000 = 107) separated by blanks. N is underground. It means that there is a treasure on the Nth floor, and H is the initial physical strength (physical strength at the stage of arriving at the basement 1st floor of the dungeon) and the maximum physical strength (recovery does not make the physical strength larger than H). ).

In the following N − 1 line, two integers are written separated by a space. For the integers di and hi on the 1 + i line (1 ≤ i ≤ N − 1), di is from the basement i floor to the basement i. + The physical strength consumed when descending to the 1st floor, hi represents the physical strength to recover when using the spring once in the basement i floor (0 ≤ di <H, 1 ≤ hi <H).

There is a way to reach the Nth basement floor in any scoring data. Of the scoring data, 10% of the points satisfy N ≤ 1000 and H ≤ 1000. For 30% of the points, N Satisfy ≤ 1000. For 50% of the points, the minimum number of times the fountain is used does not exceed 106.

Example

Input

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


Output

10

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005


int N;
ll max_HP,HP;
ll damage[SIZE],sum_damage[SIZE],recovery[SIZE];

int main(){

	scanf("%d %lld",&N,&max_HP);

	sum_damage[0] = 0;

	for(int i = 0; i < N-1; i++){

		scanf("%lld %lld",&damage[i],&recovery[i]);

		if(damage[i] >= max_HP){

			printf("-1\n");
			return 0;
		}

		sum_damage[i+1] = sum_damage[i]+damage[i]; //累積和にする
	}

	deque<int> DEQ;

	ll ans = 0;
	HP = max_HP;

	for(int i = 0; i <= N-2; i++){

		/*過去に、【とある階で回復していた】ことに【変更】する場合、【既に食らったダメージ】を再び被ることはないので、
		 * ■■■無駄(=上限による回復の打ち切り)が発生しない限り■■■、回復量が大きい泉で回復していたことにするのが良いはず。
		 * HPの折れ線グラフを、より少ない回数で、必要な分だけ上にシフトさせるということ★*/

		while(DEQ.empty() == false && recovery[DEQ.back()] <= recovery[i]){

			DEQ.pop_back(); //回数の最小化を図っているので、階iの回復量以下の泉は不要。過去使っていたことにすると損になるため
		}
		DEQ.push_back(i); //この階の泉

		while(DEQ.empty() == false && sum_damage[i]-sum_damage[DEQ.front()] >= max_HP){
			/*最大HP以上に、移動の間に体力を失うならば、もうその泉は忘れて良い
			 * →仮にその泉で完全回復したとしても、現在の体力が増えないため*/

			DEQ.pop_front();
		}

		if(HP <= damage[i]){ //何もしなければ死ぬ場合

			for(int k = 0; k < DEQ.size(); k++){

				ll theory_max = max_HP-(sum_damage[i]-sum_damage[DEQ[k]]); //階DEQ[k]で完全回復した場合に、今のHPがいくらになっているか

				if(theory_max <= HP){
					/*
					 * 仮に階DEQ[k]で完全回復したとしても現在のHPは増えないのでSKIP
					 * */
					continue;
				}

				ll need_HP = damage[i]+1; //死なないために必要な最少の体力

				ll limit = min(theory_max,need_HP)-HP; //今回の回復量の上限:回数の最小化を図るため

				/*DEQには回復量の降順にデータが入っており、かつ【過去の行動を変えたとしても、現在までに食らったダメージは変化しないため】
				 * 【無駄が生じない限り】は、選択肢の中で最大の回復量を誇る階DEQ[k]で回復するのが最適なはず。
				 * 上限の存在による【無駄】が発生した場合は、DEQ[k+1]で回復した方が
				 * 現在のHPが高くなる可能性があるので、残りの【回復し切らなかった分(limitの残り)】について
				 * 再帰的に調べる必要がある
				 * HPの折れ線グラフは、無駄(上限による回復の打ち切り)を生じさせなかった場合、
				 * 階DEQ[k]においてのHPは、ぴったりmax_HP,またはそれ未満になるはずであり、
				 * その位置までグラフをシフトさせるための必要回数は、回復量が選択肢の中で最大であるが故に、
				 * 最も効率が良いはず
				 * */

				int count = limit/recovery[DEQ[k]];
				HP += recovery[DEQ[k]]*count; //★★★確定回復量★★★
				ans += count;

				if(limit%recovery[DEQ[k]] == 0){ //階DEQ[k]で無駄が生じなかった場合

					if(HP == need_HP){ //十分回復

						break;

					}else{ //need_HPでないということはHP==theroy_maxであるはずなので、次の泉を見に行く

						continue;
					}
				}

				//階DEQ[k]で無駄が生じた場合(回復しきらなかった分がある場合)

				if(k+1 == DEQ.size()){ //もう泉が残っていない場合→階iの泉→最後の一回もこの階で回復

					HP = min(HP+recovery[DEQ[k]],max_HP);
					ans++;

				}else{ //最後の1回を、DEQ[k]での回復に使うべきか、DEQ[k+1]での回復に使うべきかを【再帰的に】検討する

					/*最後の1回を、階DEQ[k]での回復に充てる場合*/
					ll past_HP = HP+(sum_damage[i]-sum_damage[DEQ[k]]); //階DEQ[k]でHPがいくつだったか【回復しきらなかった分があるため、max_HPではあり得ない】
					past_HP = min(past_HP+recovery[DEQ[k]],max_HP); //あと1回、階DEQ[k]で回復した場合の、階DEQ[k]でのHP
					ll tmp_HP = past_HP-(sum_damage[i]-sum_damage[DEQ[k]]); //この場合、現在(階i)のHPはいくつになるか


					/*最後の1回を、階DEQ[k+1]での回復に充てる場合*/
					ll past_HP_next = HP+(sum_damage[i]-sum_damage[DEQ[k+1]]); //次の階でのHPがいくつあったか
					past_HP_next = min(past_HP_next+recovery[DEQ[k+1]],max_HP);

					ll tmp_HP_next = past_HP_next-(sum_damage[i]-sum_damage[DEQ[k+1]]); //階DEQ[k+1]で回復していたとしたら、現在のHPはいくつか

					if(tmp_HP >= tmp_HP_next){ //階DEQ[k]を採用した方が現在のHPが高くなる場合、または同じである場合

						ans++; //階DEQ[k]でもう1回回復
						HP = tmp_HP;

					}else{

						continue; //判断を保留【再帰的に論理が伝播するため】
					}
				}

				if(HP >= need_HP)break;
			}
		}

		HP -= damage[i];

		if(HP <= 0){
			printf("-1\n");
			return 0;
		}
	}

	printf("%lld\n",ans);

	return 0;
}


```