접수 처리기 대수 산정

문제

병원 예약 접수 시스템의 하루 로그를 바탕으로 접수 처리기 대수를 정하려 한다. 요청은 모두 N건이며, i번째 요청은 시각 t_i(분)에 도착하고 처리하는 데 p_i분이 걸린다. 도착 시각은 입력 순서대로 t_1 ≤ t_2 ≤ ... ≤ t_N이며, 같은 시각에 여러 건이 도착할 수 있다. 요청은 입력 순서대로 하나의 대기열에 줄을 선다. 처리기는 K대이고 성능이 모두 같으며 한 번에 한 요청만 처리한다. 앞선 요청이 모두 시작된 뒤에, 도착한 요청이 대기열의 맨 앞이고 비어 있는 처리기가 있으면 곧바로 처리가 시작된다. 처리기가 시각 x에 일을 마치면 같은 시각 x에 새 요청을 시작할 수 있고, 요청이 도착한 시각에 이미 빈 처리기가 있으면 기다리지 않고 시작한다. 요청의 대기 시간은 처리 시작 시각에서 도착 시각을 뺀 값이다. 모든 요청의 대기 시간이 W 이하가 되게 하는 가장 작은 처리기 대수 K를 구하고, 그 K대로 처리했을 때 마지막으로 끝나는 요청의 종료 시각, 즉 모든 요청의 (시작 시각 + p_i) 중 최댓값을 함께 구한다. 비어 있는 처리기가 둘 이상일 때 어느 것을 쓰는지는 결과에 영향을 주지 않는다. K = N이면 모든 요청이 대기 없이 시작하므로 조건을 만족하는 K는 언제나 존재한다.

입력

첫 줄에 정수 N, W가 공백으로 구분되어 주어진다. 이어지는 N개의 줄에 i번째 요청의 t_i, p_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ W ≤ 10^9, 0 ≤ t_1 ≤ t_2 ≤ ... ≤ t_N ≤ 10^9, 1 ≤ p_i ≤ 10^9이다. 모든 값은 정수이다.

출력

가장 작은 K와 그때의 마지막 종료 시각을 공백으로 구분해 한 줄에 출력한다.

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

2 7

3 0
0 5
0 5
0 5

3 5

2 100
0 10
1 10

1 20

출처: Devin.KR 자체 제작