U611875 种植

你总共有 $n$ 个种子，第 $i$ 个种子需要在室内连续培育 $p_i$ 天才能长成幼苗，之后将它移栽到室外，再经过 $q_i$ 天后就会结出一个美味度为 $r_i$ 的果实。移栽幼苗、为室外的幼苗浇水以及收取成熟的果实花费的时间对于你来说可以忽略不计，但由于长成幼苗前的植株照顾起来比较麻烦，你每天最多只会照顾一棵室内的植株。 具体来说，如果你在第 $t_0$ 天开始室内培育第 $i$ 个种子，那么它的室内培育工作会占用你的第 $t_0, t_0+1, \dots, t_0+P_i-1$ 天，并会在 $t_0+P_i+Q_i-1$ 天结出果实。在第 $t_0, t_0+1, \dots, t_0+P_i-1$ 天，你不会开始或同时培养其他种子。 在接下来的 $T$ 天内，你最多能收获果实的美味度总和最大是多少？注意，即使一个幼苗在第 $T$ 天前已经被移出了室外，只要它在 $T$ 天内没能结出果实，它的美味度就不会被计算到总美味度中。

第一行，两个整数 $n$ 与 $T$. 第二到 $n+1$ 行，每行用三个数表示 $p_i,q_i,r_i$.

一个整数，表示你在 $T$ 天内收获果实美味度总和的最大值。

对于 $20\%$ 的数据，$1 \le T \le 1500,1 \le n \le 30$. 对于 $100\%$ 的数据，$1 \le T \le 20000,1 \le n \le 300,1 \le p_i,q_i,r_i \le 2000$.