객실 생수 상자

문제

한 호텔은 단체 손님들의 예약에 맞추어 객실에 제공할 생수를 한 번에 준비한다. 이번 준비 목록에는 N개의 객실 예약이 있다. 각 예약에는 해당 객실에 머무는 손님 수와 숙박하는 밤의 수가 적혀 있다. 호텔은 모든 예약에 필요한 생수를 계산한 뒤, 창고에서 생수 상자를 가져오려 한다. 손님 한 명에게는 도착한 날 생수 한 병을 제공한다. 또한 숙박하는 각 밤이 지난 다음 날 아침마다 생수 한 병을 추가로 제공한다. 마지막으로 숙박한 밤의 다음 날 아침에도 제공하므로, d박을 하는 손님 한 명에게 제공하는 생수는 모두 d+1병이다. 객실에 머무는 손님 수는 예약 기간 내내 변하지 않으며, 모든 손님은 예약에 적힌 밤의 수만큼 숙박한다. 호텔은 손님에게 제공하는 생수와 별도로, 각 객실 예약마다 예비 생수 두 병을 더 준비한다. 예비 생수는 손님 한 명당 두 병이 아니라 예약 하나당 두 병이다. 예비 생수는 숙박 기간 전체에 대해 한 번만 준비하므로 숙박하는 밤의 수와 관계없이 두 병을 더하면 된다. 준비 목록의 각 줄은 별개의 예약이며, 손님 수와 숙박 기간이 같은 줄이 여러 개 있더라도 모두 계산에 포함한다. 생수는 한 상자에 정확히 K병씩 들어 있다. 창고에는 상자가 충분히 많지만 낱병으로 가져올 수는 없다. 필요한 생수를 모두 마련할 수 있도록 상자 수를 정하되, 가져오는 상자 수가 가장 작아야 한다. 가져온 상자의 생수는 모든 예약에 함께 사용할 수 있으므로 객실별로 상자를 따로 배정하지 않는다. 필요한 병 수가 K의 배수이면 남는 생수는 0병이다. 준비해야 할 생수를 배정한 뒤 남는 병 수까지 계산하는 프로그램을 작성한다.

입력

첫째 줄에 객실 예약 수 N과 상자당 생수 병 수 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000이다.
다음 N개 줄에 손님 수 g와 숙박하는 밤의 수 d가 공백으로 구분되어 주어진다. g와 d는 정수이며 1 ≤ g ≤ 10, 1 ≤ d ≤ 30이다.

출력

첫째 줄에 가져와야 하는 최소 상자 수와, 모든 예약에 필요한 생수를 배정한 뒤 남는 생수 병 수를 공백으로 구분하여 출력한다.

3 12
2 2
1 3
3 1

2 2

2 5
1 1
2 1

2 0

1 100
1 1

1 96

출처: Devin.KR 자체 제작