Basic Knapsack II

Basic Knapsack II

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

李子明用时光机成功地回到了大队长选举刚开始的时候,这次他决定谨言慎行,尽可能避免一切不确定因素。
不过,由于时间线变动,外部的环境发生了一些变化。旺仔牛奶的生产商为了挽回公司常年亏损的颓势,决定放手一搏,几乎霸占了全市大街小巷的流动广告位。他们还斥巨资邀请全市中小学的“学习之星”“文艺之星”为他们做代言,在这种宣传攻势下,旺仔牛奶几乎成了中小学生聚会、交友的标配。这一剧变也使得李子明必须对他的模型进行调整:他有\(N\)名拉票的潜在目标,其中第\(i\)人 收到\(t_i\)罐旺仔牛奶,就会使李子明的人气值增加\(c_i\)。不过旺仔牛奶也不是万能的,第\(i\)个人最多只会收下\(m_i \times t_i\)罐,如果给得过多,对方就会认为李子明没有诚意,只是单纯地想利用他,于是他为李子明“贡献”的人气值会直接归零。
请你帮李子明同学计算,若经费允许他购买不多于\(T\)罐旺仔牛奶,那么他最多可以为自己争取到多少人气值?

I/O格式

输入

第一行是一个正整数\(G\),表示测试数据的组数。对于每组数据:
第一行是两个正整数\(N, T\)。之后\(N\)行依次描述每名同学的信息,每行三个正整数\(m_i, t_i, c_i\)。

输出

每组数据输出一行。对于每组数据,输出一个整数表示李子明可以获得的最大人气值收益。

样例

输入

3
2 10
2 2 4
3 3 7
2 10
1 2 4
3 3 7
2 10
5 2 4
1 3 7

输出

22
21
20

数据规模及约定

20%的数据:\(m_i = 1\)
50%的数据:\(m_i \le 5\)
100%的数据:\(G \le 5, \quad N \le 60, \quad T \le 2 \times 10^4, \quad m_i \le 10^3, \quad t_i \le T, \quad c_i \le 10^3\)
时间限制1s,空间限制256MB。

2019.1.31测验

未参加
状态
已结束
规则
OI
题目
3
开始于
2019-01-31 14:00
结束于
2019-01-31 17:30
持续时间
3.5 小时
主持人
参赛人数
29