점검 뒤 필요한 게임 서버

문제

한 게임의 운영 담당자는 정기 점검이 끝난 직후 사용할 서버 수를 계산하고 있다. 게임 이용자는 서로 독립된 여러 구역에 나뉘어 있으며, 각 구역에 배정할 서버 수를 따로 정해야 한다. 서버 한 대에는 최대 K명의 이용자를 배정할 수 있다. 모든 서버의 수용 인원은 같으며, K는 모든 구역에 공통으로 적용된다. 각 구역에 대해서는 점검 직전 접속자 수 A, 점검 중 접속을 종료한 이용자 수 B, 점검이 끝나자마자 새로 접속한 이용자 수 C가 주어진다. 접속을 종료한 이용자는 점검 직전 접속자에 포함되어 있다. 새로 접속한 이용자는 이들과 겹치지 않는다. 따라서 점검 직후 해당 구역에 남는 이용자 수는 A에서 B를 빼고 C를 더한 값이다. 운영 담당자는 각 구역의 모든 이용자를 수용하면서 서버 수를 가능한 한 적게 배정한다. 서버 한 대에 K명보다 적은 이용자를 배정해도 되지만, K명을 넘게 배정할 수는 없다. 이용자가 한 명도 없는 구역에는 서버를 배정하지 않는다. 각 이용자는 정확히 한 대의 서버에 배정된다. 서로 다른 구역의 이용자는 같은 서버를 사용할 수 없다. 한 구역의 마지막 서버에 빈자리가 있더라도 다른 구역의 이용자를 그 자리에 배정하지 않는다. 따라서 모든 구역의 이용자 수를 먼저 합쳐서 서버 수를 계산하면 실제 필요한 서버 수와 달라질 수 있다. 모든 구역의 정보를 읽고, 점검 직후 전체 이용자 수와 필요한 서버 수의 합계를 구하는 프로그램을 작성한다. 입력에 등장하는 구역은 모두 계산에 포함한다. 전체 이용자가 한 명도 없으면 두 합계는 모두 0이며, 서버 수와 이용자 수는 소수점 없이 정수로 나타낸다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000이다.
다음 N개 줄에 각 구역의 정수 A, B, C가 주어진다. 0 ≤ A ≤ 1,000, 0 ≤ B ≤ A, 0 ≤ C ≤ 1,000이다.

출력

점검 직후 전체 이용자 수와 각 구역에 필요한 최소 서버 수의 합계를 공백으로 구분하여 한 줄에 출력한다.

3 4
5 1 2
4 4 0
2 0 1

9 3

2 10
3 3 0
0 0 0

0 0

2 5
1 0 0
1 0 0

2 2

출처: Devin.KR 자체 제작