스마트 홈 전력의 꼭대기

문제

스마트 홈 관리기는 여러 기기의 예약 작동 기록을 모아 공용 전원 장치가 감당해야 할 전력을 계산한다. 관리 대상 시간은 기준 시각부터 100,000초 동안이며, 기준 시각을 0초라고 부른다. 모든 예약은 정수 초에 시작하고 정수 초에 끝난다. 예약 하나는 시작 시각 S, 종료 시각 E, 소비 전력 P로 이루어진다. 이 예약은 S초부터 E초 직전까지 P만큼의 전력을 사용한다. 즉, 정수 t에 대해 S ≤ t < E이면 구간 [t, t+1)에서 이 예약의 전력이 사용된다. 종료 시각 E부터는 해당 전력을 사용하지 않는다. 서로 다른 예약은 같은 기기의 기록이라도 독립된 전력 항목으로 취급한다. 따라서 여러 예약이 겹치는 동안의 전체 소비 전력은 그 예약들의 P를 모두 더한 값이다. 관리기는 최대 소비 전력뿐 아니라 그 상태가 언제 처음 나타났고 모두 몇 초 동안 이어졌는지도 보고해야 한다. 여기서 최대 상태의 총시간은 최대 소비 전력이 나타난 모든 1초 구간의 개수를 뜻한다. 최대 상태가 중간에 끊겼다가 다시 나타나면, 끊긴 시간은 제외하고 각 구간의 길이를 더한다. 첫 발생 시각은 최대 소비 전력이 나타나는 1초 구간 중 가장 이른 구간의 시작 시각이다. 예약의 입력 순서는 시작 시각이나 종료 시각과 관계없다. 또한 한 예약이 끝나는 시각에 다른 예약이 시작할 수 있다. 같은 시각의 시작과 종료는 모두 그 시각 이후의 소비 전력에 반영되므로, 처리 순서 때문에 실제로 존재하지 않는 순간적인 최댓값을 만들어서는 안 된다. 전력을 사용하는 예약이 없는 시간의 소비 전력은 0이다. 주어진 모든 예약을 반영하여 관리 대상 시간 전체에서의 최대 소비 전력, 그 전력이 처음 나타나는 시각, 그 전력이 나타난 총시간을 구한다. 예약은 적어도 하나이며 각 예약의 소비 전력은 양수이므로 최대 소비 전력도 항상 양수다.

입력

첫째 줄에 예약 수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개 줄에 정수 S, E, P가 주어진다. 0 ≤ S < E ≤ 100,000이고, 1 ≤ P ≤ 999다. 시각의 단위는 초이며 소비 전력의 단위는 모든 기록에서 동일하다.

출력

최대 소비 전력, 그 전력이 처음 나타나는 시각, 그 전력이 나타난 총시간을 순서대로 공백으로 구분하여 정수로 출력한다. 같은 최댓값이 여러 구간에서 나타나면 첫 발생 시각은 가장 작은 시각으로 정하고, 총시간에는 모든 해당 구간의 길이를 더한다.

4
1 4 3
2 3 5
5 7 8
7 8 2

8 2 3

3
0 2 4
2 5 4
2 4 1

5 2 2

1
9 10 7

7 9 1

출처: Devin.KR 자체 제작