题目描述

李子明用时光机成功地回到了大队长选举刚开始的时候，这次他决定谨言慎行，尽可能避免一切不确定因素。
不过，由于时间线变动，外部的环境发生了一些变化。旺仔牛奶的生产商为了挽回公司常年亏损的颓势，决定放手一搏，几乎霸占了全市大街小巷的流动广告位。他们还斥巨资邀请全市中小学的“学习之星”“文艺之星”为他们做代言，在这种宣传攻势下，旺仔牛奶几乎成了中小学生聚会、交友的标配。这一剧变也使得李子明必须对他的模型进行调整：他有\(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。