Live Programming

A famous Japanese idol group, JAG48, is planning the program for its next live performance. They have $N$ different songs, $\mathit{song}\_1$, $\mathit{song}\_2$, ..., and $\mathit{song}\_N$. Each song has three integer parameters, $t\_i$, $p\_i$, and $f\_i$: $t\_i$ is the length of $\mathit{song}\_i$, $p\_i$ is the basic satisfaction points the audience gets when $\mathit{song}\_i$ is performed, and $f\_i$ is the feature value of $\mathit{song}\_i$ that affects the audience's satisfaction. During the live performance, JAG48 can perform any number (but at least one) of the $N$ songs, unless the total length of the chosen songs exceeds the length of the live performance $T$. They can decide the order of the songs to perform, but they cannot perform the same song twice or more.

The goal of this live performance is to maximize the total satisfaction points the audience gets. In addition to the basic satisfaction points of each song, the difference between the feature values of two songs performed consecutively affects the total satisfaction points. If there is no difference, the audience feels comfortable. The larger the difference, however, the more frustrated the audience feels.

Thus, the total satisfaction points are calculated as follows:

• If $\mathit{song}\_x$ is the first song of the live performance, the total satisfaction points just after $\mathit{song}\_x$ is $p\_x$.
• If $\mathit{song}\_x$ is the second or a later song and is performed just after $\mathit{song}\_y$, $p\_x - (f\_x - f\_y)^2$ is added to the total satisfaction points, because the audience feels frustrated when $f\_x$ and $f\_y$ differ.

Help JAG48 find a program with the maximum total satisfaction points.

The input is formatted as follows.

$N$ $T$

$t_1$ $p_1$ $f_1$

$\ldots$

$t_N$ $p_N$ $f_N$

The first line contains two integers $N$ and $T$: the number of available songs $N$ ($1 \le N \le 4{,}000$), and the length of the live performance $T$ ($1 \le T \le 4{,}000$).

The following $N$ lines give the parameters of the songs. The $i$-th of them contains three integers, the parameters of $\mathit{song}\_i$: the length $t\_i$ ($1 \le t\_i \le 4{,}000$), the basic satisfaction points $p\_i$ ($1 \le p\_i \le 10^8$), and the feature value $f\_i$ ($1 \le f\_i \le 10^4$).

You can assume that at least one song has length at most $T$.

Output the maximum total satisfaction points the audience can get during the live performance.