콘서트홀 일정 짜기

당신은 파산 위기에 놓인 유명 콘서트홀을 구하기 위해 관장으로 임명되었다. 이 콘서트홀은 매우 인기가 많아 두 개의 훌륭한 공연장을 쓰고 싶다는 신청이 많이 들어오지만, 전임 관장이 비효율적이었던 탓에 여러 해 동안 적자를 보고 있다. 두 공연장은 크기와 구조가 완전히 같으므로, 공연을 열려는 신청자는 어느 쪽인지 지정하지 않고 그냥 공연장 하나를 요청한다. 각 공연장은 하루에 한 공연만 열 수 있다.

수익을 늘리기 위해, 당신은 기존의 정찰제를 버리고 신청자가 스스로 낼 금액을 제시하게 하기로 했다. 각 신청은 기간 $[i, j]$와 희망 금액 $w$를 제시한다. 여기서 $i$와 $j$는 각각 기간의 첫날과 마지막 날이며 ($1 \le i \le j \le 365$), $w$는 신청자가 그 기간 전체 동안 공연장 하나를 쓰기 위해 낼 금액(엔)으로 양의 정수이다.

당신은 내년 치 신청을 모두 받았고, 이제 어떤 신청을 받아들일지 정해야 한다. 각 신청은 그 기간 전체를 받아들이거나 아예 거절해야 하며, 받아들인 공연은 그 기간 내내 같은 공연장을 써야 한다.

콘서트홀의 절박한 재정 상황을 고려하여 예술성은 무시하고, 가장 수익성 높은 신청들을 받아들여 한 해 전체의 총수입을 최대로 하라.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 신청의 개수를 나타내는 정수 $n$이 적힌 줄로 시작한다. 이어서 $n$개의 줄에 각 신청이 기간 $[i, j]$와 희망 금액 $w$(엔)로 다음 형식으로 주어진다.

i j w

$0$ 하나만 있는 줄은 입력의 끝을 나타낸다.

한 데이터셋의 신청은 최대 1000개이며, 희망 금액은 최대 100만 엔이다.

각 데이터셋에 대해, 그 데이터셋에서 얻을 수 있는 최대 총수입(엔)을 정수 하나로 한 줄에 출력한다.