问题陈述

一支著名的日本偶像团体 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

```plain
200```

---

### 示例输入 2

```plain
3 15
5 100 1
5 100 2
5 100 4```

### 示例输出 2

```plain
295```

---

### 示例输入 3

```plain
3 10
5 200 200
5 200 201
5 300 1```

### 示例输出 3

```plain
399```

---

### 示例输入 4

```plain
3 20
5 100 200
5 100 201
5 300 1```

### 示例输出 4

```plain
300```

---

### 示例输入 5

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

### 示例输出 5

```plain
103```