상담원

시간 제한8초메모리 제한512 MB

요약
끊긴 뒤 다시 전화하는 고객들을 시뮬레이션하고, 모든 통화가 시간 T 안에 끝나는 최소 상담원 수를 구한다.
난이도

보통10점 중 7점

유형
시뮬레이션, 이분 탐색, 구현, 그리디
정답자
아직 제출이 없습니다

문제

컴퓨터 판매 회사 JAG의 고객 전화 상담 센터는 지금 큰 혼란에 빠져 있다. 상담을 요청하는 고객이 너무 많고, 그 고객들이 쉴 새 없이 전화를 건다. 회사는 이 상황을 감당하려면 상담원이 몇 명 필요한지 알아내려고 한다.

문제를 단순하게 만들기 위해 다음 시뮬레이션만 생각한다.

고객은 NN명이고, ii번 고객의 번호는 ii이다. 각 고객은 세 정수 MiM_i, LiL_i, KiK_i로 정해진다. 상담원이 ii번 고객을 상담하는 데 MiM_i 단위 시간이 걸린다. ii번 고객은 전화를 건 시각부터 LiL_i 단위 시간이 지날 때까지 어느 상담원도 응답하지 않으면 전화를 끊는다. 전화를 끊고 KiK_i 단위 시간 뒤에 다시 건다. 전화를 건 시각부터 정확히 LiL_i 단위 시간이 되는 순간에 상담원이 응답하면 통화는 연결되고, 그 순간까지 아무도 응답하지 않으면 고객은 끊는다.

상담원 한 명은 동시에 한 고객만 상담한다. 상담을 마친 상담원은 곧바로 다른 전화를 받을 수 있다. 기다리는 고객이 여럿이면 상담원은 번호가 가장 작은 고객을 고른다.

시뮬레이션이 시작될 때 모든 고객이 동시에 상담 센터로 전화를 건다. 모든 고객의 상담이 TT 단위 시간 안에 끝나면 시뮬레이션은 성공이다. 정확히 TT 단위 시간에 끝나는 상담도 제때 끝난 것으로 친다.

시뮬레이션을 성공시키는 데 필요한 상담원의 최소 인원을 구하라.

입력

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N T
M1 L1 K1
.
.
.
MN LN KN

각 데이터 세트의 첫 줄에 양의 정수 NN과 TT가 주어진다 (1≤N≤10001 \le N \le 1000, 1≤T≤10001 \le T \le 1000). NN은 고객 수, TT는 시뮬레이션의 제한 시간이다.

이어지는 NN개 줄에 고객 정보가 주어진다. ii번째 줄에는 세 정수 MiM_i, LiL_i, KiK_i가 주어진다 (1≤Mi≤T1 \le M_i \le T, 1≤Li≤10001 \le L_i \le 1000, 1≤Ki≤10001 \le K_i \le 1000).

입력의 끝은 0 두 개만 있는 줄로 표시한다. 이 줄은 어느 데이터 세트에도 속하지 않으므로 처리하지 않는다.

출력

각 데이터 세트마다 시뮬레이션을 성공시키는 데 필요한 상담원의 최소 인원을 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    3 300
100 50 150
100 50 150
100 50 150
3 300
100 50 150
100 50 150
200 50 150
9 18
3 1 1
3 1 1
3 1 1
4 100 1
5 100 1
5 100 1
10 5 3
10 5 3
1 7 1000
10 18
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 11
10 11 12
0 0
    예상 출력
    2
3
3
4

  2. 예제 2

    입력
    3 6
2 100 1
2 100 1
2 100 1
3 5
2 100 1
2 100 1
2 100 1
0 0
    예상 출력
    1
2