문제
당신은 던젼의 지하 N층에 있는 어떤 보물을 손에 넣고 싶다. 맨 처음 당신은 지하 1층에 있고 당신의 체력은 H (H는 양의 정수)이다. 아래층으로 내려갈 경우 체력은 감소하게 된다. 한번 아래층으로 내려가면, 보물을 손에 넣을때까지 윗층으로 돌아오는것은 불가능 하다. 한편 각층에는 1개의 체력 회복의 샘물이 있는데, 샘물을 1회 사용했을 때 회복가능한 체력은 각각 정해져 있다. 체력이 0 이하가 되면 당신은 죽게 된다. 또, 체력이 H보다 높아지는 경우는 없다. 회복의 샘물의 사용횟수는 제한이 없지만 회복에는 시간이 걸리기 때문에, 샘물의 사용을 가능한 한 적게 해야한다. N, H, 각층의 아래로 내려갈때 감소되는 체력과 각 층의 회복의 샘물을 1회 사용하면 회복되는 체력이 주어졌을때, 체력을 0이하로 만들지 않으면서 지하 N층까지 도착하기 위해 필요한 샘물의 사용횟수의 최소값을 구하는 프로그램을 작성하여라.
입력
입력의 첫째 줄에는 두개의 정수 N, H (2≤N≤100,000, 1≤H≤10,000,000)가 공백으로 구분되어 써있다. N은 지하 N층에 보물이 있는것을 나타내고, H는 최초 체력값 (던전의 지하 1층에 도착했을 때의 체력)이자, 체력의 최대값이다. (회복으로 체력이 H보다 더 커지는것은 불가능하다.) 이어지는 N-1행에는, 2개의 정수가 공백으로 구분되어 써있다. 1+i 행째에는 (1≤i≤N-1)인 정수 di, hi 에 대해, di는 지하 i층 부터 지하 i+1층에 내려갈 때 소비되는 체력을, hi 는 지하 i층의 샘을 1회 사용했을 때 회복되는 체력을 나타낸다. (0≤di＜H, 1≤hi＜H). 모든 입력에 대해서 지하 N층에 도달하는 방법이 존재한다.
출력
체력을 0 이하로 만들지 않고 지하 N층에 도달하기 위해 필요한 체력 회복 물약의 최소 사용수를 출력하라. 다루는 정수의 범위가 32bit를 넘을 가능성이 있으니 주의하라.
예제
10 10
4 2
2 5
6 1
7 3
6 4
9 6
0 8
4 1
9 4
10
로그인해야 코드를 작성할 수 있어요.