← 返回题目列表

AtCoder · icpc2015summer_day4_i

I. 现场编程

中文机器翻译题面 查看原题

问题陈述

日本著名偶像团体JAG48正在规划下一次现场演出的节目。 他们有 $N$ 首不同的歌曲:$\mathit{song}_1$、$\mathit{song}_2$、...和 ​​$\mathit{song}_N$。 每首歌曲有$t_i$、$p_i$和$f_i$三个整数参数:$t_i$表示$\mathit{song}_i$的长度,$p_i$表示$\mathit{song}_i$表演时观众获得的基本满意度分,$f_i$表示$\mathit{song}_i$影响观众满意度的特征值。 在现场表演期间,JAG48可以表演任意数量(但至少一首)$N$歌曲,除非所选歌曲的总长度超过现场表演的长度$T$。 他们可以决定歌曲的表演顺序,但不能将同一首歌表演两次或多次。

本次现场表演的目标是最大限度地提高观众的总满意度。 除了每首歌曲的基本满意度外,连续表演的两首歌曲的特征值差异也会影响总满意度。 如果没有差别的话,观众就会觉得舒服。 然而,差距越大,观众就越沮丧。

因此,总满意分将计算如下:

  • 如果$\mathit{song}_x$是现场表演的第一首歌,则$\mathit{song}_x$之后的总满意分等于$p_x$。
  • 如果$\mathit{song}_x$是现场表演的第二首或后续歌曲,并且在$\mathit{song}_y$之后表演,则将$p_x - (f_x - f_y)^2$添加到总满意分中,因为如果$f_x$和$f_y$不同,观众会感到沮丧。

帮助JAG48找到总满意度最高的节目。


输入

输入的格式如下。

$N$ $T$
$t_1$ $p_1$ $f_1$
$\ldots$
$t_N$ $p_N$ $f_N$

第一行包含两个整数 $N$ 和 $T$: 可用歌曲的数量 $N$ ($1 \le N \le 4{,}000$),以及现场表演的长度 $T$ ($1 \le T \le 4{,}000$)。

接下来的$N$行代表歌曲的参数。 其中第$i$行包含三个整数,它们是$\mathit{song}_i$的参数: 长度$t_i$ ($1 \le t_i \le 4{,}000$),基本满意度点$p_i$ ($1 \le p_i \le 10^8$),以及特征值$f_i$ ($1 \le f_i \le 10^4$)。

您可以假设至少有一首歌曲的长度小于或等于 $T$。

输出

输出观众在现场表演过程中可以获得的最大总满意度分。


示例输入 1

2 10
10 200 1
10 100 100

样本输入 1 的输出

200

示例输入 2

3 15
5 100 1
5 100 2
5 100 4

样本输入 2 的输出

295

示例输入 3

3 10
5 200 200
5 200 201
5 300 1

样本输入 3 的输出

399

示例输入 4

3 20
5 100 200
5 100 201
5 300 1

样本输入 4 的输出

300

示例输入 5

5 61
14 49 7
31 46 4
30 55 5
52 99 1
34 70 3

样本输入 5 的输出

103