问题陈述
日本著名偶像团体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