Concert Hall Scheduling

Time limit2sMemory limit128 MB

Summary

Given up to 1000 interval requests with prices for two identical rooms over 365 days, select accepted intervals (assignable to either of 2 rooms without overlap) to maximize total revenue.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Intervals
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples4

Example 1

Input

4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640
0

Expected output

30
25500
38595

Example 2
Input
```
1
1 365 100
0
```
Expected output
```
100
```
Example 3
Input
```
3
1 5 10
1 5 20
1 5 30
0
```
Expected output
```
50
```
Example 4
Input
```
2
1 10 5
11 20 7
0
```
Expected output
```
12
```