冲神与列车

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
30.00%(6/20)
Description:

Z市新开通一班从A1出发开往A100站的列车途径站A1,A2,A3...A99,A100。车票在列车开动之前进行预订,乘客可以预订从x站到y站的车票(1<=x在乘车时,从x站上车,y站下车出于列车运行成本的考虑,列车上的座位数要尽量少,但同时又要让所有购票的乘客都有座位,且不发生冲突。乘务员姐姐小明想请冲神写一个程序,计算出列车所需最小座位数,使得列车正常运行(所有的乘客都有位置坐,且不发生冲突)。冲神日理万机,还有更重要的事情要处理,那么就请你帮帮忙吧!


注意:一个位置可以被使用多次。例如从站2到站5的乘客可以和从站11到站15的乘客使用同一个座位。

Input:

题目包含多组测试数据。输入都是整数。在每一组输入中第一行代表预订的个数n(0<=n<=1000),接下来将会有n行,每一行有三个数s,d,h表示h个座位从站As到站Ad

n=0时表示输入结束。

Output:

对于每一组输入数据,请你计算出列车正常运行所需最小的座位数。

Sample Input:
2
1 10 3
20 30 4
3
1 20 4
15 25 3
11 30 5
0
Sample Output:
4
12

Submit