上分
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在Codeforces赛制中,每道题都会根据难度赋予不同的基础分(保证基础分一定是250的倍数).

在比赛过程中,分数会不断衰减,具体的规则是每过一分钟每道题的分数会减少基础分的0.4\%.

假设一道题的基础分为500分,那么如果在比赛开始1分钟后通过了这道题,那么能获得498分,如果在第3分钟通过了这道题,那么能获得494分,每道题都只会在第一次通过时获得分数.

对于每次错误的提交会扣除对应的题目50分,但是保证每道题通过时所得的分数不会低于基础分的30\%.

在每场比赛结束后,总得分越多的选手排名越高.

小菲正在准备参加某场Codeforces比赛,突然某种神秘力量降临,小菲知道了她在这场比赛中每道题需要花费多长时间可以通过,并且还知道了每道题她在通过之前会错误提交多少次.

她想请你安排一下她做题的顺序,让她获得最高的得分.

当然,每场比赛都有时间限制,小菲不一定能在比赛结束之前通过所有题目.


输入描述:

本题含有多组测试数据.
第1行包含一行一个正整数T(1 \leq T \leq 10),表示测试数据的数目,然后输入T组独立的数据.

每组数据第1行输入一行以空格分隔的2个正整数n, m(1 \leq n \leq 9, 1 \leq m \leq 180),分别表示比赛的题目数量和持续时间(以分钟为单位).

接下来输入n行,每行输入以空格分隔的3个非负整数a_i, b_i, c_i(1 \leq i \leq n),分别表示第i题的基础分,小菲通过第i道题需要的时间(以分钟为单位)和小菲在通过第i题之前错误提交的次数.

对于所有数据中的a_i,b_i,c_i,有500 \leq a_i \leq 3000, 1 \leq b_i \leq 180, 0 \leq c_i \leq 100,且保证a_i是250的倍数.

输出描述:

对于每组数据,输出一行一个非负整数表示小菲在比赛中能获得的最高得分.
示例1

输入

复制 
1
2 120
500 60 0
1000 60 1

输出

复制 
970

说明

样例中比赛总时长为120分钟,有2道题目.
小菲的一种最优策略是先完成第2道题目,此时距离比赛开始60分钟,并且该题有一次错误提交.能获得分值1000 \cdot(1 - 0.004 \cdot 60) - 50 = 710.然后完成第1道题目,此时距离比赛开始120分钟.能获得分值500 \cdot(1 - 0.004 \cdot 120) = 260.因此获得的最高总得分为710 + 260 = 970.