반납 서가의 저녁 기록

문제

도서관은 반납된 책을 임시 서가에 모은 뒤, 정리가 끝난 책을 다른 서가로 옮긴다. 담당자는 매일 업무가 끝났을 때 임시 서가에 남은 책의 수를 기록한다. 첫 번째 날의 업무를 시작하기 직전에는 책이 B권 있으며, 임시 서가의 권장 보관량은 C권이다. 권장 보관량은 운영상 정한 기준이므로 이를 넘어서더라도 책을 계속 놓을 수 있다. 하루의 업무는 두 단계로 진행된다. 먼저 그날 반납된 책 R권을 임시 서가에 놓고, 이어서 정리가 끝난 책 M권을 임시 서가에서 꺼낸다. 따라서 그날 저녁의 책 수는 전날 저녁의 책 수에 R을 더하고 M을 뺀 값이다. 첫 번째 날에는 전날 저녁의 책 수 대신 B를 사용한다. 꺼내는 책의 수는 그 시점에 임시 서가에 있는 책의 수를 넘지 않는다. 담당자는 N일의 기록으로 세 가지 값을 구하려 한다. 첫 번째 값은 저녁의 책 수가 C를 처음으로 초과한 날의 번호다. 두 번째 값은 저녁의 책 수가 C를 초과한 날의 총개수다. 세 번째 값은 N번의 저녁 기록 중 가장 큰 책 수다. 날의 번호는 첫 번째 날부터 1, 2, …, N으로 붙인다. 권장 보관량과 정확히 같은 날은 초과한 날에 포함하지 않는다. 반납 직후 잠깐 권장 보관량을 넘었더라도, 책을 꺼낸 뒤의 저녁 기록이 기준 이하라면 그날은 포함하지 않는다. 업무 시작 전의 B 역시 저녁 기록이 아니므로 최댓값을 구할 때 따로 포함하지 않는다. 초과한 날이 여러 번 나타나면 첫 번째 값에는 가장 이른 날을 사용하며, 한 번도 초과하지 않았다면 첫 번째 값과 두 번째 값은 모두 0이다.

입력

첫째 줄에 정수 N, C, B가 공백으로 주어진다. 1 ≤ N ≤ 50,000, 0 ≤ C ≤ 1,000,000,000, 0 ≤ B ≤ 1,000,000,000이다.
다음 N개 줄의 i번째 줄에 i일의 정수 R_i와 M_i가 공백으로 주어진다. 0 ≤ R_i, M_i ≤ 9이다. 매일 M_i는 전날 저녁의 책 수에 R_i를 더한 값 이하임이 보장된다. 첫 번째 날에는 전날 저녁의 책 수를 B로 본다.

출력

권장 보관량을 처음 초과한 날의 번호, 초과한 날의 총개수, 저녁에 남은 책 수의 최댓값을 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 초과한 날이 없으면 앞의 두 값은 0이다.

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

2 2 12

3 5 0
0 0
5 0
0 5

0 0 5

출처: Devin.KR 자체 제작