描述

你被任命为一家著名音乐厅的主任，以拯救它免于破产。该音乐厅非常受欢迎，收到了许多使用其两个精美房间的申请，但不幸的是，前任主任效率不高，多年来一直在亏损。这两个房间的大小和布局相同。因此，每个希望举办音乐会的申请人都会要求一个房间，但不会特别指定哪一个。每个房间每天只能用于一场音乐会。

为了赚取更多收入，你决定放弃之前的固定价格政策，而是让申请人指定他们愿意支付的价格。每个申请人都会指定一个时间段 $[i, j]$ 和一个出价 $w$，其中 $i$ 和 $j$ 分别是该时间段的第一天和最后一天（$1 \leq i \leq j \leq 365$），$w$ 是一个正整数，以日元表示，表示申请人愿意支付的金额，用于在该时间段内使用一个房间。

你已经收到了下一年的申请，现在应该选择你将接受的申请。每个申请应该被完全接受或完全拒绝。每场音乐会应该在整个申请期间使用同一个房间。

鉴于音乐厅严峻的经济形势，艺术质量可以忽略不计，你应该尝试通过接受最有利可图的申请来最大化全年的总收入。

输入

输入包含多组数据，每组数据以一个整数 $n$ 开始，表示该数据集中的申请数量。然后是 $n$ 行，每行表示一个申请，包含一个时间段 $[i, j]$ 和一个出价 $w$（单位：日元），格式如下：

i j w

包含单个零的行表示输入结束。

数据集中申请的最大数量为一千，最大出价为一百万日元。

输出

对于每个数据集，打印一行，包含一个整数，表示该数据集的最大总收入（单位：日元）。

输入数据 1

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

输出数据 1

30  
25500  
38595

来源

2003年日本，会津