小红升装备
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红准备去打boss了，为了强化自己的战力，小红准备精心打磨自己的装备。
现在给定了每个装备初始的战力，购买每个装备的价格，每个装备强化一级花费的金币和可以提升的战力，以及每个装备最大可以提升的等级。（装备刚购买的时候为初始状态：0级）
小红最初的金币为x，她想知道，自己可以通过强化装备最多达到多少战力？
请注意，装备只有购买了才可以强化！

输入描述:

第一行输入两个正整数n,x，代表装备数量和小红初始拥有的金币。
接下来的n行，每行输入5个正整数att_i,price_i,cost_i,upgrade_i,lvmax_i，分别代表装备初始战力，购买该装备需要的金币、升1级花费的金币、升1级提升的战力、最高可以提升的等级。
1\leq n,x \leq 300
1\leq att_i,price_i,cost_i,upgrade_i,lvmax_i \leq 10^9

输出描述:

一个整数，代表小红可以达到的最大战力。
示例1

输入

复制 
3 10
10 3 5 2 100
100 20 5 4 100
20 2 1 10 1

输出

复制 
40

说明

小红购买第一个和第三个装备，花费5金币，然后花费1金币给第三个装备升1级，该装备的战力提高到30。此时还剩4金币已经无法再升级装备。
最终的战力为40。