《群星》(Stellaris) 是 Paradox 出品的一款战略游戏。P社游戏还有《文明》、《欧陆风云》等，但是很奇怪，ZJY 好像只玩《群星》。
不同于其他P社游戏的是，《群星》的背景是 2200 年众多已经拥有超光速航行能力的大型星系文明。玩家所掌控的文明可以干很多事情，包括建造舰队。
舰队是一组舰船的集合。舰船可以有詹姆级护卫舰、肖浩级驱逐舰、诺克瑞兹级战列舰等等，ZJY 一共设计了 nnn 种舰船，每种舰船有战斗力 viv_ivi。一支舰队只能指挥一定的舰船，它的指挥值有上限 MMM，其中每种舰船占用指挥值 mim_imi。你的文明已经拥有了戴森球，财力雄厚，锻造业发达，可以承担任意数量的建造。
另外，《群星》还规定了一些超大型舰船的建造数量有上限，比如泰坦和巨像，第 iii 种舰船的建造上限为 kik_iki。这些舰船也占用指挥值。
ZJY 想知道，对于他设计的这些舰船，可以建造的舰队战斗力最强为多少？舰队的战斗力为舰船战斗力之和。
第一行两个整数表示 nnn 和 MMM； 接下来 nnn 行，每行表示一种舰船，有三个数 mim_imi, viv_ivi, kik_iki，表示指挥值、战斗力和建造数量限制，ki=−1k_i = -1ki=−1 表示可以无限建造。
输出一行一个整数，表示一支舰队的最强战斗力
样例输入 1
2 10 3 7 1 2 4 -1
样例输出 1
20
样例输入 2
5 50 2 8 5 3 9 -1 10 45 1 12 18 -1 5 19 126
样例输出 2
199
1≤n≤200,1≤M≤2×1051 \le n \le 200, 1 \le M \le 2 \times 10^51≤n≤200,1≤M≤2×105
1≤mi≤2×1051 \le m_i \le 2 \times 10^51≤mi≤2×105
1≤vi≤1091 \le v_i \le 10^91≤vi≤109
ki∈{−1}∪[1,109]∩Z+k_i \in \{-1\} \cup [1, 10^9] \cap \mathbb{Z}_+ki∈{−1}∪[1,109]∩Z+
