천문대의 두 관측 기록

문제

한 천문대는 밤에 사용할 망원경 한 대의 관측 계획을 세우고 있다. 연구원들은 관측 후보 N개를 제출했다. 각 후보에는 관측을 시작하는 시각, 끝내는 시각, 그리고 그 관측으로 얻을 자료의 가치가 적혀 있다. 후보에는 제출된 순서대로 1번부터 N번까지 번호가 붙어 있다. 후보 번호의 순서와 관측 시각의 순서는 서로 관계가 없다. 천문대는 이 후보 중 서로 다른 두 개를 정확히 선택하려고 한다. 선택한 두 관측은 망원경 한 대로 차례로 진행할 수 있어야 한다. 후보 i의 시작 시각을 S_i, 종료 시각을 E_i라고 할 때, 관측이 망원경을 사용하는 시간 구간은 S_i 이상 E_i 미만이다. 따라서 한 관측이 끝나는 시각에 다른 관측을 바로 시작하는 것은 가능하다. 두 관측 사이에 비어 있는 시간이 있어도 괜찮다. 두 후보 i와 j를 함께 선택할 수 있는 조건은 E_i ≤ S_j 또는 E_j ≤ S_i이다. 이 조건을 만족하지 않으면 두 관측의 사용 시간이 겹치므로 함께 선택할 수 없다. 장비 준비와 방향 전환에 필요한 시간은 각 후보의 시간에 이미 포함되어 있으며, 별도의 시간을 더하지 않는다. 후보의 시작 시각이나 종료 시각을 바꾸거나 관측을 중간에 나누는 것은 허용하지 않는다. 선택한 두 관측의 총가치는 두 후보에 적힌 가치의 합이다. 천문대는 함께 선택할 수 있는 모든 후보 쌍 중 총가치가 가장 큰 쌍을 고른다. 총가치가 같은 쌍이 여러 개라면, 각 쌍의 후보 번호를 작은 번호부터 나열한 뒤 첫 번째 번호가 작은 쌍을 고른다. 첫 번째 번호도 같다면 두 번째 번호가 작은 쌍을 고른다. 관측 두 개를 함께 선택할 수 없는 경우에는 하나만 선택하는 대신 계획을 취소한다. 모든 후보의 정보를 보고 선택할 두 후보의 번호와 총가치를 구한다. 출력하는 후보 번호는 실제 관측 진행 순서와 관계없이 작은 번호가 먼저 오도록 한다.

입력

첫째 줄에 관측 후보 수를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 200)
다음 N개의 줄 중 i번째 줄에 정수 S_i, E_i, V_i가 공백으로 구분되어 주어진다. 각각 후보 i의 시작 시각, 종료 시각, 자료의 가치이다.
0 ≤ S_i < E_i ≤ 100,000이며 1 ≤ V_i ≤ 10,000이다. 시각의 단위는 해당 밤의 기준 시각으로부터 지난 분이다. 서로 다른 후보의 정보가 모두 같을 수도 있다.

출력

함께 선택할 수 있는 후보 쌍이 있다면, 선택한 두 후보의 번호를 작은 번호부터 출력하고 그 뒤에 총가치를 출력한다. 세 정수는 공백으로 구분하여 한 줄에 출력한다. 함께 선택할 수 있는 후보 쌍이 없다면 -1만 출력한다.

5
8 12 11
0 5 7
5 8 10
4 10 30
12 15 12

4 5 42

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

1 2 10

3
1 8 4
2 6 9
3 7 6

-1

출처: Devin.KR 자체 제작