호텔 안내음 시험 시간

문제

한 호텔에서는 새 안내 방송 장치의 소리를 시험하려고 한다. 시험에는 정확히 한 시간이 걸리며, 같은 날의 정각에 시작해서 다음 정각에 끝내야 한다. 담당자는 투숙객이 제출한 조용한 시간 요청을 살펴보고, 요청에 주는 부담이 가장 작은 시작 시각을 고르려고 한다. 하루는 0시부터 24시까지이며, 선택할 수 있는 시작 시각은 정수 0, 1, …, 23이다. 시작 시각으로 h를 선택하면 시험은 h시부터 h+1시까지 진행된다. 시험은 하루에 정확히 한 번만 실시하며, 자정을 넘어가는 시험이나 시간을 나누어 진행하는 시험은 허용하지 않는다. 조용한 시간 요청은 모두 N건이다. 각 요청에는 시작 시각 A_i, 종료 시각 B_i, 중요도 W_i가 적혀 있다. 이 요청은 A_i시 이상 B_i시 미만의 시간을 조용하게 유지해 달라는 뜻이다. 시험 시작 시각 h가 A_i ≤ h < B_i를 만족하면 해당 요청의 중요도 W_i만큼 부담이 발생한다. h가 B_i와 같으면 그 요청에 대한 부담은 발생하지 않는다. 전체 부담은 영향을 받는 모든 요청의 중요도를 더한 값이다. 같은 시간 구간과 중요도를 가진 요청이 여러 건 있어도 각각 별도로 더한다. 요청의 시간 구간이 서로 겹치는 것도 허용한다. 영향을 받는 요청이 하나도 없다면 전체 부담은 0이다. 전체 부담을 최소화하는 시험 시작 시각과 그때의 부담을 구한다. 최소 부담을 만드는 시작 시각이 여러 개라면 가장 이른 시각을 선택한다. 모든 요청은 같은 날 안의 유효한 구간이며, 요청 때문에 특정 시작 시각을 선택하지 못하는 경우는 없다.

입력

첫째 줄에 요청 수를 나타내는 정수 N이 주어진다. 다음 N개 줄의 i번째 줄에 정수 A_i, B_i, W_i가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 20,000
0 ≤ A_i < B_i ≤ 24
1 ≤ W_i ≤ 100
입력에 등장하는 모든 수는 정수다.

출력

선택한 시험 시작 시각과 그 시각의 전체 부담을 공백으로 구분하여 한 줄에 출력한다. 시작 시각은 0부터 23까지의 정수로 출력한다.

3
0 8 4
7 24 3
10 12 8

8 3

2
2 5 9
8 10 2

0 0

출처: Devin.KR 자체 제작