Concert Hall Scheduling

You have been appointed director of a famous concert hall to save it from bankruptcy. The hall is very popular and receives many requests to use its two fine rooms, but the previous director was not efficient and it has been losing money for years. The two rooms are identical in size and layout, so each applicant simply asks for a room without specifying which one. Each room can host only one concert per day.

To make more money, you have decided to drop the old fixed-price policy and instead let applicants name the price they are willing to pay. Each application specifies a period $[i, j]$ and an asking price $w$, where $i$ and $j$ are the first and last days of the period ($1 \le i \le j \le 365$) and $w$ is a positive integer number of yen — the amount the applicant will pay to use a room for the entire period.

You have received all applications for the next year and must decide which to accept. Each application must be either accepted for its whole period or rejected completely, and an accepted concert must use the same room for its entire period.

Given the hall's dire finances, ignore artistic quality and simply maximize the total income for the year by accepting the most profitable set of applications.

The input has multiple datasets. Each dataset starts with a line containing a single integer $n$, the number of applications. It is followed by $n$ lines, each describing one application with a period $[i, j]$ and an asking price $w$ yen in the format:

i j w

A line containing a single zero indicates the end of the input.

A dataset contains at most one thousand applications, and the maximum asking price is one million yen.

For each dataset, print a single line containing one integer: the maximum total income in yen for that dataset.