TopCoder

User's AC Ratio

61.5% (8/13)

Submission's AC Ratio

29.0% (9/31)

Description

琵歐伯,一個終年下雨不停的音樂之城。這個城市裡有全國最好的音樂學院,也聚集了許多想成為音樂家的人。

琵歐伯音樂學院最重要的大事就是每年一月的畢業演奏會,全校的畢業生都必須上台表演。畢業演奏會對琵歐伯音樂學院的學生來說是非常重要的一次演出,表現優異的話可能會被外面的知名樂團看上,順利踏入音樂界。

本故事的主角 A 就是琵歐伯音樂學院的學生(*A為什麼叫*A呢,聽說是因為他把 A 演算法用得出神入化,於是被同學們尊稱為 A* 之神。不知道為什麼有次倒過來變成 A,之後大家就跟著這樣叫了),主修的樂器是「符德魯琴」。這種樂器和一般樂器最不同的地方是,符德魯琴需要注入魔力才能演奏,需要極高的天份,一般人是學不來的。符德魯琴並不適合單獨演奏,通常符德魯琴系的畢業生都會找聲樂系的學生合奏。為此,A 要在這兩個月中找出最適合和他搭配的人,才能演奏出最完美的音樂。

其實 *A 並不是應屆畢業生,他是以非常優秀的成績申請跳級,所以比正常的畢業生還小了一歲。這樣的特殊身份對他好有壞,壞處是他跟大一屆的聲樂系學長姊不太熟,還沒有固定的搭擋。好處是全聲樂系的學生都知道 *A 的符德魯琴非常好聽,人又很正,不論男女都想跟他合作演出。

*A 利用他的優勢找了 n(n ≦ 1000)個學姊(*A 是個大色鬼只找學姊不找學長),分別問了她們有空一起練習合奏的時間。很巧的是每個人有空的時間都是一段連續的日期,其中第 i 個學姊有空的時間是從今天開始算 Ri 天後到 Di 天後(包含頭尾這兩天)。合奏是為了計算兩個人之間的「適合度」,要計算和學姊 i 的「適合度」至少要 Pi 次的合奏才行。

A 是個大忙人,除了要準備畢業演奏之外還有很多約會,所以每天最多只能和一個人合奏。他希望能夠在畢業演奏會之前多和幾個學姊試試看,想請你幫他完成這個程式,讓他找到最好的搭擋,要是之後順利成為知名的音樂家,A 絕對不會忘記你的!

Input Format

輸入檔包含多組測試資料。每組測試資料的第一行是一個整數 n。接下來 n 行每行有三個正整數,其中第i行依序是 Ri Di Pi (0 < Ri, Di, Pi ≦ 10000000, Ri < Di),且滿足(R1 ≦ R2 ≦ ... ≦ Rn, D1 ≦ D2 ≦ ... ≦ Dn)。讀到 n = 0 的時候代表檔案的結尾,不需要對於這個數字作任何輸出。

Output Format

對每組測試資料,輸出一個整數表示最多能算出幾個學姊的「適合度」。

Sample Input

3
1 4 3
2 6 4
5 6 2
0

Sample Output

2

Hints

Problem Source

原TIOJ1100 / NPSC2006決賽(prob C)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536