U143777 Sans的审判

aaa 今天真幸运，家长不在家。于是他赶紧打开刚下的盗版 ut。开心的玩起了游戏，可他打的是屠杀线，而技术又很蒟蒻，所以在 Sans 那里死了无数次。于是他决定再打一遍。

我们已知蒟蒻 aaa 的能力为 $W$，Sans 前还有 $N$ 个怪，每杀一个怪可以得到 $g$ 个金钱和 $a$ 点 LOVE 值(暴力指数)，而不愧是盗版 ut，每饶恕一个怪可以减少(?) $b$ 点 LOVE 值，但没有金钱。 aaa 是个守财奴，他既想打过 Sans 又想获得足够的金钱。而众所周知 Sans 的能力等于 aaa 的 LOVE 值。 但他家长还有一秒就回来了，现在只有求助学 OI 的你，请你设计一个程序，算出他在打过 Sans 的前提下（包括他们能力相等）最多可获得的金钱数。

第一行，两个整数：怪的个数 $N$,aaa 的能力值 $W$。 下面 $N$ 行，每行三个字母：$g, a, b$。 $g_i,a_i,b_i$ 分别表示第 $i$ 个怪杀掉所得的金币数和增加的 LOVE 值和饶恕减少的 LOVE 值。 题目保证最后可以打过 Sans。

一行，一个整数 $ans$，即最多得到的金币数。

对于 $25$% 的数据，$1 \leqslant n \leqslant 5$; 对于剩下$25$%数据 $20 \leqslant n \leqslant 200$,$1 \leqslant g_{i} \leqslant 1e6 $; 对于剩下$50$%数据 $1 \leqslant w \leqslant 1000 $,$1 \leqslant g_{i} \leqslant 5e6 $,$1 \leqslant a_{i},b_{i} \leqslant 50 $。