首頁  題目列表  狀態列表  排行榜  註冊  帳號: 密碼:
公告:支援C++11 (2014/08/18 21:39)
Problem 0094 : 致兩千年後的你
0094 -- 致兩千年後的你
Case Time Limit: 3000 ms    Memory Limit: 65536 KB
Total Testdata Count: 5
AC/Submit: 22/28    AC/Submit Users: 9/9

[回到列表]
題目敘述



身為一名職業級的秀吉控,你,もも,又開始了你的一天。
但是今天早上你卻發現了一件不得了的事!
你平常一邊觀察秀吉一邊寫的日記“秀吉日記” 今天一整天的份竟然已經寫好了!
「難道 這就是...」
「沒錯 這就是你的“未來日記“ ,“秀吉日記“能以毫秒為單位記錄秀吉身邊所發生的任何事情,與將會發生的所有事情。我是機械的神明--maki,是可以實現任何願望的萬能許願機!」
「你說什麼!? 我竟然許了這種願望!?」


(秀吉)

就這樣,你得到了你的未來日記。
身為一名世界第一的秀吉控,你當然要好好活用你的未來日記,以毫秒為單位繼續的跟蹤秀吉,但同時你也從你的未來日記得知了許多不得了的事情..
「什麼!? “時刻65536ms 秀吉會被路邊的比利告白”」
諸如此類的未來預言不斷出現
「不行,全世界的偽娘都是我的啊啊啊啊啊啊!」
你,もも, 今天化身狂戰士, 打算把所有接近秀吉的人殺掉!但是要殺的人實在太多(畢竟是以毫秒為單位不停的出現),
因此你為了節省時間與力氣決定只挑發生順序相鄰的$N$個人出來殺掉,並且達到殺雞儆猴的效果。

所謂發生順序相鄰定義為:
對於事件$\xi \neq \zeta$,令兩事件將要發生的時刻分別為$T_\xi , T_\zeta$且$T_\xi \le T_\zeta$,
若不存在事件$\sigma$使得$T_\xi \le T_\sigma \le T_\zeta$,
則$\xi , \zeta$是相鄰的兩事件。

為了達到最佳的警告效果,我們依照未來日記上所記載的每一個人的情報,分析出兩項數值,殺掉他對周圍人們的警告效果和殺掉他時噴出的番茄汁量。
已知殺掉第$i$個人的警告效果$a_i$和此人被殺掉時噴出的番茄汁量$b_i$成正相關,問你為了達到最佳的警告效果,共會撒出多少公升的番茄汁呢?
若是有一種以上警告效果同樣好的方法,則噴的番茄汁愈多愈好。

輸入說明

輸入的第一行有兩個正整數$K, N$代表你今天的未來日記裡共有$K$筆記錄,並且你要挑出$N$個人來開刀
接下來的$2 \sim K+1$行每行有三個正整數
對於第$i$行的三個正整數$T_i, a_i, b_i$代表時刻$T_i$有一個人接近了秀吉,殺了他的話會得到$a_i$的警示效果,並噴出$b_i$公升的番茄汁

輸出說明

輸出一個正整數$\lambda$代表番茄汁的總量

範例輸入

6 3
300 4 8
45 5 6
100 8 9
254 16 80
367 100 100
124 100 1


範例輸出

90


備註

對於範例輸入,選擇發生時刻100、124、254的連續三個人所得到的警示效果$8 + 100 + 16 = 124$最大

同一筆測資中任兩筆事件發生時刻必定不同

你可以假設對於每筆測資$\lambda$必定在unsigned int可以儲存的範圍內

$1 \leq N \leq K \leq 10^6$
$1 \leq T_i, a_i, b_i, \leq {2}^{32}-1$

測資

測資組A : 1~1 (1筆測資),20 分
測資組B : 2~2 (1筆測資),20 分
測資組C : 3~3 (1筆測資),20 分
測資組D : 4~4 (1筆測資),20 分
測資組E : 5~5 (1筆測資),20 分
[回到列表]