山寨華山論劍 (AP325 P-6-16)

自從華山論劍聲名大噪之後，很多人都想參加，但 \(20\) 年辦一次實在太久了，五輪奧運都跑 \(5\) 趟了，於是各地都紛紛舉辦華山論劍，往往同一天就有很多場。每一場都有自己的開始時間與結束時間，參加者必須全程在場，所以兩場的時間如果有重疊就不能同時參加。令狐沖本來想參加最多場來盡速累積經驗值，但後來他發現有很多場次能獲得的經驗值很少，參加了反而浪費時間，現在要請你幫忙計算最多可以得到的經驗值總和。請注意，所挑選活動必須完全不重疊，兩場活動只在端點重疊也是不可以同時參加的，也就是說前一場的結束時間必須小於下一場的開始時間。

輸入格式

第一行是一個正整數 \(n\)，代表一共舉辦了 \(n\) 場華山論劍，接下來 \(n\) 行，每行有三個非負整數 \(s\)、\(t\) 與 \(e\)，代表這場活動時間區間是 \([s, t]\)，而可以得到的經驗值是 \(e\)，數字間以空白間隔。

限制

• \(n\) 不超過 \(10^5\)。
• \(s < t < 10^9\)。
• 答案不超過 \(10^9\)。

輸出格式

輸出最大可能經驗值總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

3
1 2 1
2 3 3
3 4 1

範例輸出 1

3

範例輸入 2

3
1 2 2
2 3 3
3 4 2

範例輸出 2

4

範例說明

範例一：挑選 \([2, 3]\)，得到經驗值 \(3\)。

範例二：挑選 \([1, 2]\) 與 \([3, 4]\)，得到經驗值 \(2 + 2 = 4\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 P-6-16，第 194 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。