Dungeon

You want to obtain the treasure on basement floor $N$ of a dungeon. At first you are on basement floor 1, and your stamina is $H$ (a positive integer). Descending to the next floor down consumes stamina, and the amount consumed when descending from each floor is known in advance. In addition, every floor has one healing spring; each time you use the spring on a floor, you recover an amount of stamina fixed for that floor. If your stamina drops to $0$ or below, you die. Your stamina can never exceed $H$. You may use the springs any number of times, but healing takes time, so you want to use the springs as few times as possible.

Given $N$, $H$, the stamina consumed when descending from each floor, and the stamina recovered by one use of each floor's spring, write a program that computes the minimum number of spring uses needed to reach basement floor $N$ without ever letting your stamina drop to $0$ or below.

Also, once you descend to a lower floor, you can never return to an upper floor until you obtain the treasure.

The first line contains two integers $N$ and $H$ separated by a space ($2 \le N \le 10^5$, $1 \le H \le 10^7$). $N$ means the treasure is on basement floor $N$, and $H$ is your initial stamina (your stamina upon arriving on basement floor 1) as well as the maximum possible stamina (healing never raises your stamina above $H$).

Each of the following $N-1$ lines contains two integers separated by a space. On line $i$ ($1 \le i \le N-1$), the integers $d_i$ and $h_i$ satisfy $0 \le d_i < H$ and $1 \le h_i < H$: $d_i$ is the stamina consumed when descending from basement floor $i$ to basement floor $i+1$, and $h_i$ is the stamina recovered by one use of the spring on basement floor $i$.

Output, on a single line, the minimum number of spring uses needed to reach basement floor $N$ without ever letting your stamina drop to $0$ or below.

Note that the integers handled in this problem may not fit in 32 bits.