著名的日本偶像团体 JAG48 正在为她们的下一场现场演出规划节目。她们有 $N$ 首不同的歌曲，分别为 $song_1, song_2, \dots, song_N$。每首歌都有三个整数参数：$t_i, p_i$ 和 $f_i$。其中 $t_i$ 表示 $song_i$ 的时长，$p_i$ 表示演唱 $song_i$ 时观众获得的基础满意度，$f_i$ 表示影响观众满意度的 $song_i$ 的特征值。在现场演出中，JAG48 可以表演 $N$ 首歌曲中的任意数量（但至少要表演一首），前提是所选歌曲的总时长不超过演出总时长 $T$。她们可以决定表演歌曲的顺序，但不能重复表演同一首歌。

本次演出的目标是使观众获得的总满意度最大化。除了每首歌的基础满意度外，连续表演的两首歌的特征值之差也会影响总满意度。如果特征值没有差异，观众会感到舒适。然而，差异越大，观众就会越感到沮丧。

因此，总满意度的计算方式如下：

• 如果 $song_x$ 是演出的第一首歌，则 $song_x$ 表演后的总满意度等于 $p_x$。
• 如果 $song_x$ 是演出的第二首或后续歌曲，且紧接在 $song_y$ 之后表演，则在总满意度中增加 $p_x - (f_x - f_y)^2$，因为如果 $f_x$ 和 $f_y$ 不同，观众会感到沮丧。

请帮助 JAG48 找到一个能获得最大总满意度的节目安排。

输入格式

第一行包含两个整数 $N$ 和 $T$：可用歌曲的数量 $N$ ($1 \le N \le 4000$) 以及演出总时长 $T$ ($1 \le T \le 4000$)。

接下来的 $N$ 行表示歌曲的参数。第 $i$ 行包含三个整数，即 $song_i$ 的参数：时长 $t_i$ ($1 \le t_i \le 4000$)，基础满意度 $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