11908 - Skyscraper

有一棟超高大樓的管理委員會打算在他們大樓的外牆設置廣告，他們找來的客戶要求把特定大小的廣告放置在特定的高度，且願意付出不同的價格。每個廣告主要求放置廣告在特定的高度(由廣告版面所在最低的樓層開始算起)、特定大小(廣告版面所佔據的樓層數)，且必須完整地佔據整層大樓的外牆，不會有多個廣告在同一層的情況。每個廣告都有其價格，當然，廣告不能被分割、不能被放置在非指定樓層，否則拿不到廣告收益。

問題是有許多廣告可能會涵蓋相同樓層而產生衝突，這時候就必須做取捨，本題請你在符合廣告配置規定的情況下，選出最佳的配置方式以達到收益最大化。

Input

輸入的第一列有一個整數T(<= 50)表示測試資料的組數。

每組測試資料一開始會給定整數N(1 <= N <= 30000)表示廣告的數量，接下來會有N列分別為各個廣告的資訊，每則廣告以三個整數表示，A(0 <= A <= 10^5)，B(1 <= B <= 10^5)，C(1 <= C <= 1000)，分別表示最低所在樓層、佔據的樓層數與廣告收益。

Output

請輸出每組測試資料的最大廣告收益。

Sample Input	Output for Sample Input
1 3 1 5 1 2 10 3 7 12 1	Case 1: 3

---

原文出處