UOJ Logo Sharp Sword 剑锋 OI

SSOI

#55. score

统计

【问题描述】

一场比赛有n道题,比赛总时间为t。
第i道题目的初始分值为Ai(Ai<=10^6)分,之后每过1分钟,这道题的分值就会减少Bi,并且保证比赛结束时分值不会减少为负值。比如,一个人在第x分钟结束时做出了第i道题目,可以得到Ai-Bi*x分。
若一位选手在第x分钟结束时做完了一道题,则可以在第x+1分钟立即开始做另外一道题目。
dxy大牛会做所有的题,但由于比赛时间限制,他可能无法完成所有的题,求比赛结束前最多可以得到多少分。已知dxy第i道题目花费Ci(Ci<=t)分钟。

【输入格式】

第一行为一个正整数T(T<=10),表示数据组数(n>200的数据不超过5组)。
对于每组数据,第一行为两个正整数n(n<=1000)和(t<=3000),分别表示题目数量和比赛时间。接下来有n行,每行3个正整数依次表示Ai,Bi,Ci,即此题的初始分值、每分钟减少的分值、dxy做这道题需要花费的时间。

【输出格式】

对于每组数据输出一行一个整数,代表dxy这场比赛最多能得多少分。

【输入样例1】

1
4 10
110 5 9
30 2 1
80 4 8
50 3 2

【输出样例1】

88

【时空限制】

对于35%的数据,n<=10,t<=50;
对于另外的20%的数据,Bi=0;
还有另外20%的数据,Bi=1
对于100%的数据,n<=1000,t<=3000;
时间限制:2S
空间限制:256MB