정리까지 끝나는 회의

문제

한 공동 사무실에는 예약해서 사용하는 회의실이 하나 있다. 운영 담당자는 하루 동안 들어온 회의 신청 가운데 일부를 승인하려 한다. 각 신청에는 회의를 시작할 시각, 회의를 끝낼 시각, 회의가 끝난 뒤 정리에 필요한 시간이 적혀 있다. 시각은 운영을 시작한 순간부터 지난 분 수로 나타낸다. 회의가 시작하면 신청에 적힌 종료 시각까지 회의실을 사용한다. 종료 직후에는 신청한 정리 시간만큼 회의실을 계속 비워 두어야 한다. 정리 중에는 다른 회의를 시작할 수 없다. 시작 시각이 S, 종료 시각이 E, 정리 시간이 C인 신청을 승인하면 회의실은 S 이상 E+C 미만의 시각에 다른 신청을 위해 사용할 수 없다. 다음 회의는 정확히 E+C에 시작해도 된다. 정리 시간이 0이면 회의 종료 시각에 바로 다음 회의를 시작할 수 있다. 각 신청의 시작 시각과 종료 시각은 이미 정해져 있어 옮길 수 없다. 회의 시간을 줄이거나 정리를 나누어 진행하는 것도 허용하지 않는다. 승인한 회의끼리는 회의와 정리를 모두 포함한 사용 구간이 겹치지 않아야 한다. 승인하지 않은 신청은 회의실 사용에 아무런 영향을 주지 않는다. 처음에는 회의실이 비어 있으며 모든 신청을 거절해도 된다. 운영 담당자의 목표는 승인하는 신청 수를 가장 크게 만드는 것이다. 회의 길이나 정리 시간이 길다고 추가 점수를 주지는 않으며, 모든 신청은 승인했을 때 정확히 한 건으로 센다. 시작 시각, 종료 시각, 정리 시간이 모두 같은 신청이 여러 개 들어올 수도 있다. 이 경우에도 각각 별도의 신청이지만, 사용 구간이 겹치는 신청을 동시에 승인할 수는 없다. 승인할 수 있는 신청 수의 최댓값을 구한다. 최댓값을 만드는 승인 목록이 여러 개여도 목록 자체는 출력하지 않는다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 15,000이다.
다음 N개 줄에 각 신청의 정수 S, E, C가 공백으로 주어진다. 0 ≤ S < E ≤ 1,000,000이며 0 ≤ C ≤ 999이다. 신청은 임의의 순서로 주어진다. 정리가 끝나는 시각이 1,000,000을 넘어도 유효한 신청이다.

출력

승인할 수 있는 신청 수의 최댓값을 정수 하나로 출력한다. 승인 가능한 신청이 없다면 0을 출력한다.

5
0 3 2
3 4 0
4 6 1
5 7 0
7 8 0

3

4
2 5 3
2 5 0
5 6 0
6 7 0

3

출처: Devin.KR 자체 제작