说明

本题需要使用文件重定向，输入输出文件名cyber.in/cyber.out

题目描述

在 2077 年，由于地球资源即将枯竭，能源危机也即将爆发。而在此时，人类发现了一种新的物质：赛博粒子。这种粒子通常具有非常大的能量，而如果人类能够很好地利用这种粒子所蕴含的能量，那么就可以很好地避免这场能源危机的爆发。于是，众多科学家对其展开了研究。

这种粒子的能量并不是一成不变的，并且并非所有赛博粒子的能量变换都相同。于是，科学家收集了 $n$ 种不同的赛博粒子，每一种赛博粒子仅有一个。对于第 $i$ 种粒子来说，刚开始收集到的时候的能量为 $a_i$，而其每经过 $t$ 秒，能量就会变成 $a_i - t\times b_i$，注意能量可能减到负数。

为了使得能量可控，科学家们发明了一种机器，可以固定赛博粒子的能量。另外，机器固定每一个粒子所需要的时间是不同的。固定一个第 $i$ 种的粒子需要的时间为 $c_i$ 秒。另外，这个固定粒子能量的机器有一个限制：同一时刻只能固定一个粒子，并且一旦开始固定，这个过程就必须等到固定完成才能继续下一次固定工作。

科学家们想研究如下问题：给定时间限制 $C$ 秒，在这 $C$ 秒之内能够固定下来的粒子的能量之和最大可以是多少？由于科学家们没学过算法，所以他们来找你寻求帮助。

输入格式

第一行输入两个正整数 $n, C$，表示收集到的粒子种类数和时间限制。

接下来 $n$ 行，每行输入三个非负整数 $a_i, b_i, c_i$，含义见题面。

输出格式

输出一行一个整数，表示能够固定下来的粒子的能量之和的最大值。

样例

3 10
15 2 3
11 1 7
18 3 1

22

样例解释 1

先固定第 三 个粒子，固定需要 1 秒，固定后能量为 15，此时第一个粒子的能量为 13，第二个粒子的能量为 10；

之后如果固定第一个粒子，则需要 3 秒，固定后的能量为 $13-2\times 3=7$，固定的粒子能量一共为 22；

如果固定第二个粒子，则需要 7 秒，固定后的能量为 $10 - 1\times 7 = 3$，固定的粒子能量一共为 18。

故答案为 22。

10 100
1405 1120 2
81030 1066 4
2327 1996 7
73870 1450 1
61478 1705 6
62949 1572 5
99179 1355 5
49322 1709 2
75088 1246 6
5893 1408 2

373496

样例输入 3

见选手下发文件 cyber_sample3.in

样例输出 3

见选手下发文件 cyber_sample3.out

数据范围

本题的各个测试点对应的数据范围如下表所示。

测试点编号	$n$	$C$	特殊范围
1	$\leqslant10$	$\leqslant10$	无
2
3
4		$\leqslant100$
5
6
7	$\leqslant50$	$\leqslant10$
8
9	$=$1	$\leqslant10^5$
10
11	$\leqslant50$		$b_i=0$
12
13			$c_i=1$
14
15			无
16
17
18
19
20

对于 100% 的数据，$1\le n \le 50, 1\le C,c_i \le 10^5, 0 \le a_i,b_i\le 10^5$

来源

by Vingying