nodgd是一个喜欢写程序的同学，前不久洛谷OJ横空出世，nodgd同学当然第一时间来到洛谷OJ刷题。于是发生了一系列有趣的事情，他就打算用这些事情来出题恶心大家……
最近，洛谷OJ效仿codeforces又出了一种新的刷题比赛模式——计分比赛。每次不是按照通过的数据数量排名，而是一个“保密”的规则来统计选手们的得分，最后按照得分来排名。排名前五的选手都将得到一份神秘的实物奖品。
nodgd同学对这个新规则很好奇，历经千辛万苦终于找到了这个计分的规则，如下：一次共有N道题的比赛时间限制是T。每道题有两个参数，s[i]和ds[i]，如果你在t时刻AC了这道题，你将会得到s[i]-t*ds[i]的得分(显然你可能会被倒扣分，但是你也可以选择不做这个题)。选手们可以随意的安排做题顺序，也不一定要把每道题都做完，只需尽量得高分就行了。
nodgd同学在事先就预估好了自己每道题需要的时间ci，想知道自己最多可以在这次比赛中得到多少分。不过nodgd同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题……要做，就拜托你来帮他算算了。

第一行两个正整数N,T，表示有N道题，时间限制是T分钟。
第二行到第N+1行，第i+1行有三个正整数s[i],ds[i],c[i]，表示第i题的两个参数和需要的时间。

共一行，一个非负整数，表示最多能得到的分数。

2<=N<=30
1<=T<=200000
1<=s[i]<=10^9
1<=ds[i]<=1000
1<=c[i]<=10000
保证答案在int范围内