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

题面描述

端午汇演完成后，同学们按照小组为单位投票。每个小组的构成不同：

​ 第$i$个小组有$a_i$位同学，重要性为$b_i$，现在组内有$c_i$位同学已经为你投了票。

如果第$i$小组有超过一半的同学为你投票，你就可以获得$b_i$朵小红花。

你拥有$m$颗糖果，给某位同学一颗糖果就可以让他把原来投给别人的票投给你！（如果一个同学已经投给了你，给他糖果不会有任何效果！）

----也就是说，假设第一小组有5个人，原来有3个人投票给你，你可以使用2颗糖果让剩下两个同学也投票给你。

请你计算一下，使用m颗糖果的情况下，最多收获多少朵小红花？

输入

第一行输入两个整数$n,m$，分别代表小组数量和糖果个数。$(1\leq n,m\leq 10^3)$

接下来的$n$行，每行输入三个整数$a_i,b_i,c_i$，分别代表第$i$小组的总人数、重要性、已为你投票的人数。$(1\leq c_i \leq a_i,b_i \leq 10^3 )$

输出

一个整数，代表使用糖果后的最多小红花获取数量。

样例输入 1

4 4
3 4 1
5 7 2
7 10 2
9 13 1

样例输出 1

21

样例解释 1

样例输入 2

4 2
3 5 2
5 8 2
5 9 1
7 4 4

样例输出 2

18

样例输入 3

3 1
5 6 1
7 10 2
9 12 1

样例输出 3

0