TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

88.2% (15/17)

Submission's AC Ratio

40.3% (29/72)

Description

什麼叫做「很忙」呢?

簡單來說,對於某一段時間(從Ai秒到Bi時間點)來說,如果我至少有整整 Ci 秒鐘是保持忙碌的,那麼我就很忙。如下圖:

我想要保持「很忙」的狀態,可是我又不想要那麼忙,給定以上的一些「很忙」的條件的話,我最少要忙多久呢?

Input Format

輸入檔可能包含多筆測試資料。每一筆測試資料的第一列有一個正整數 n (1≦n≦100,000)代表決定「很忙」的條件數量。

接下來的 n 列,每一列有三個正整數 Ai, Bi, Ci (0≦Ai, Bi, Ci≦100,000)。

當n=0的時候代表輸入結束。

Output Format

對於每筆測試資料請輸出一列包含一個數:我至少要保持忙碌多少秒鐘?

Sample Input

5
2 7 3
7 10 3
5 8 1
0 3 1
9 11 1
0

Sample Output

6

Hints

※2008/08/07:題目敘述修正,感謝ggm!by Tmt

Problem Source

原TIOJ1408 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。
(Adapted From NTU Judge 0037)

Subtasks

For Testdata: 0 ~ 0, Score: 25
For Testdata: 1 ~ 1, Score: 25
For Testdata: 2 ~ 2, Score: 25
For Testdata: 3 ~ 3, Score: 25
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 9999 65536 65536
1 9999 65536 65536
2 9999 65536 65536
3 9999 65536 65536