착유기는 몇 대가 필요할까

문제

농장의 착유장에 젖소 N마리가 차례로 찾아온다. i번째 소는 시각 a_i 에 도착하고, 착유에는 w_i 의 시간이 걸린다. 도착 시각은 입력 순서대로 줄지 않는다(같은 시각에 여러 마리가 도착할 수 있다). 착유장에는 똑같은 착유기가 M대 있으며, 소는 입력 순서대로 한 마리씩 처리한다. 소가 도착하면 그 시점까지 가장 일찍 비게 되는 착유기를 쓴다. 이미 비어 있는 착유기가 있으면 도착 즉시 착유를 시작하고, 모든 착유기가 사용 중이면 가장 먼저 끝나는 착유기가 비기를 기다린다. 따라서 i번째 소의 착유 시작 시각은 max(a_i, 선택된 착유기가 비는 시각)이고, 대기 시간은 (시작 시각 − a_i) 이다. 착유가 끝나는 시각은 시작 시각 + w_i 이며 그 순간 착유기는 바로 다음 소에게 쓸 수 있다. 착유기를 고르는 번호 규칙은 결과에 영향을 주지 않는다. 어느 소의 대기 시간도 W 를 넘지 않도록 하는 착유기 대수 M 의 최솟값을 구하라. M = N 이면 모든 소의 대기 시간이 0 이므로 답은 항상 존재한다.

입력

첫 줄에 N 과 W 가 공백으로 구분되어 주어진다. 이어지는 N 개의 줄에 i번째 소의 a_i 와 w_i 가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ W ≤ 1,000,000,000, 0 ≤ a_1 ≤ a_2 ≤ ... ≤ a_N ≤ 1,000,000,000, 1 ≤ w_i ≤ 1,000,000,000 이며 모든 값은 정수이다.

출력

조건을 만족하는 착유기 대수의 최솟값을 한 줄에 출력한다.

5 2
0 4
0 4
1 3
2 1
2 2

3

3 0
5 1
5 1
5 1

3

2 100
0 5
10 5

1

출처: Devin.KR 자체 제작