지정 세탁기의 접수 기록

문제

한 세탁소에는 번호가 붙은 세탁기 N대가 있다. 세탁기는 각각 독립적으로 작동하며, 시각 0에는 모든 세탁기가 비어 있다. 이 세탁소의 고객은 예약할 때 사용할 세탁기를 직접 지정한다. 직원은 고객의 요청을 접수 기록에 적힌 순서대로 확인하고, 요청을 받아들일지 즉시 결정한다. 각 요청에는 도착 시각 t, 지정한 세탁기 번호 m, 필요한 세탁 시간 d가 들어 있다. 요청을 확인하는 시각에 지정한 세탁기가 비어 있으면 요청을 받아들인다. 받아들인 세탁은 시각 t에 곧바로 시작하여 시각 t+d에 끝난다. 세탁기가 다른 작업을 진행하고 있다면 요청을 거절한다. 거절된 요청은 대기 목록에 넣지 않으며, 나중에 세탁기가 비더라도 다시 처리하지 않는다. 다른 번호의 세탁기가 비어 있어도 고객이 지정한 번호를 바꾸지 않는다. 세탁이 끝나는 시각부터는 해당 세탁기를 다시 사용할 수 있다. 예를 들어 어떤 세탁이 시각 12에 끝난다면, 같은 세탁기를 지정한 시각 12의 요청은 받아들일 수 있다. 여러 요청의 도착 시각이 같으면 입력에 먼저 나온 요청부터 처리한다. 따라서 같은 시각에 같은 세탁기를 지정한 요청들이 있다면 앞선 요청의 처리 결과가 뒤의 요청에 영향을 준다. 세탁 시간은 항상 양수이므로 방금 시작한 세탁이 같은 시각에 끝나는 일은 없다. 직원은 기록에 있는 요청을 모두 확인한 뒤 접수된 요청 수, 거절된 요청 수, 그리고 접수된 모든 세탁이 끝나는 마지막 시각을 보고하려 한다. 마지막 요청을 확인한 시점에 아직 진행 중인 세탁도 끝나는 시각 계산에 포함한다. 접수 기록을 따라 이 세 가지 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 세탁기 수 N과 요청 수 M이 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 25,000이다.
다음 M개 줄에 t m d가 주어진다. 0 ≤ t ≤ 100,000, 1 ≤ m ≤ N, 1 ≤ d ≤ 99이다.
도착 시각 t는 감소하지 않는 순서로 주어진다. 도착 시각이 같은 요청은 입력 순서대로 처리한다. 입력의 모든 수는 정수다.

출력

접수된 요청 수, 거절된 요청 수, 접수된 모든 세탁이 끝나는 마지막 시각을 공백으로 구분하여 한 줄에 출력한다. 접수된 요청이 없다면 마지막 시각은 0으로 출력한다.

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

4 2 8

1 4
3 1 2
3 1 1
5 1 1
6 1 4

3 1 10

출처: Devin.KR 자체 제작