마지막 상자까지

문제

한 공장은 하루 작업을 여러 차례로 나누어 진행한다. 각 작업 차례가 끝나면 생산 라인 담당자가 만든 부품 수와 그중 검사에서 제외된 부품 수를 기록한다. 검사에서 제외된 부품은 포장할 수 없으며, 나머지 부품은 모두 포장할 수 있다. 각 차례의 기록에 적힌 생산 수에는 검사에서 제외된 부품 수도 포함되어 있다. 포장 담당자는 모든 작업이 끝난 뒤 포장할 수 있는 부품을 한곳에 모은다. 따라서 서로 다른 차례에서 나온 부품을 같은 상자에 넣어도 된다. 앞선 차례에서 남은 부품을 버리거나, 차례가 바뀔 때마다 새 상자로 포장을 시작하는 일은 없다. 모든 부품의 종류와 크기는 같아서 어느 부품끼리 묶어도 포장 규칙을 만족한다. 상자 하나에는 정확히 K개의 부품을 넣는다. 부품이 K개보다 적게 남으면 그 부품들은 상자에 넣지 않고 다음 날을 위해 보관한다. 부품을 나누거나 복제할 수 없으며, 검사에서 제외된 부품으로 빈자리를 채울 수도 없다. 포장 담당자는 완전히 채운 상자의 수가 최대가 되도록 포장한다. 하루의 작업 기록은 총 N개이며, 각 기록에는 생산한 부품 수 A와 검사에서 제외된 부품 수 B가 정수로 주어진다. 같은 수가 적힌 기록도 서로 다른 작업 차례의 기록이므로 각각 반영한다. 어떤 차례에는 생산한 부품이 없을 수 있고, 생산한 부품이 모두 검사에서 제외될 수도 있다. 기록에 없는 추가 생산이나 부품의 이동은 일어나지 않는다. 모든 작업 기록과 상자 하나에 넣는 부품 수가 주어질 때, 완전히 채운 상자의 수와 포장하지 못하고 보관할 부품 수를 구한다. 포장할 부품이 하나도 없다면 두 수는 모두 0이다. 출력하는 두 수는 하루 전체의 결과이며, 작업 차례별 결과를 따로 출력하지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000이고 1 ≤ K ≤ 1,000이다.
다음 N개의 줄에는 각 작업 차례의 정수 A와 B가 공백으로 구분되어 주어진다. 0 ≤ B ≤ A ≤ 1,000이다.

출력

완전히 채운 상자의 최대 개수와 남은 부품 수를 이 순서대로 공백 하나로 구분하여 한 줄에 출력한다.

3 7
12 2
8 3
9 1

3 2

2 4
0 0
6 6

0 0

2 5
3 0
2 0

1 0

출처: Devin.KR 자체 제작