Live Programming

일본의 유명 아이돌 그룹 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$ 바로 다음에 공연되면, $f\_x$와 $f\_y$가 다를수록 관객이 답답함을 느끼므로 $p\_x - (f\_x - f\_y)^2$가 총 만족 포인트에 더해진다.

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$ 이하인 곡이 적어도 하나 존재한다고 가정할 수 있다.

라이브 공연에서 관객이 얻을 수 있는 총 만족 포인트의 최댓값을 출력한다.