F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 2131. -- 免费的馅饼

2131: 免费的馅饼

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 842  Solved: 497
[Submit][Status][Discuss]

Description

Input

第一行是用空格隔开的二个正整数,分别给出了舞台的宽度W(1到10^8之间)和馅饼的个数n(1到10^5)。  接下来n行,每一行给出了一块馅饼的信息。由三个正整数组成,分别表示了每个馅饼落到舞台上的时刻t[i](1到10^8秒),掉到舞台上的格子的编号p[i](1和w之间),以及分值v[i](1到1000之间)。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。

Output

一个数,表示游戏者获得的最大总得分。

Sample Input

3 4
1 2 3
5 2 3
6 3 4
1 1 5

Sample Output

12
【数据规模】
对于100%的数据,1<=w,t[i]<=10^8,1<=n<=100000。

HINT

Source

[Submit][Status][Discuss]

HOME Back