Dungeon

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

inputFormat

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

outputFormat

Output

10

样例

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

10