题目描述

小 C 是一名魔法师，她现在要去魔法商店购买魔法药水。魔法商店里共有 $n$ 种魔法药水，每种都有无限瓶存货。对于第 $i$ 种魔法药水，购买一瓶需要消耗 $v_i$ 块金币，使用一瓶可以得到 $w_i$ 的法力值。

经过长年的经验， 小 C 已经掌握了魔法药水的隐藏特性： 对于第 $i$ 种魔法药水，如果使用的总数量为奇数，则可以额外得到 $a_i$ 的法力值；如果使用的总数量为偶数，可以额外得到 $b_i$ 的法力值。当然， 如果某一种魔法药水没有使用， 则不会得到相应的额外法力值。

现在小 C 只有 $m$ 块金币，你需要求出她最大能得到多少法力值。

输入格式

从文件 $potion.in$ 中读入数据。 第一行两个整数 $n$, $m$，分别表示魔法药水的种类数与金币的数量。 之后 $n$ 行，每行四个整数 $v_i$ , $w_i$ , $a_i$ , $b_i$ ，含义如题目所述。

输出格式

输出到文件 $potion. out$中。 一行一个整数，表示小 C 能得到的法力值的最大值。

样例 #1

样例输入 #1

4 5
1 1 2 3
2 3 2 4
3 4 3 5
4 5 4 6

样例输出 #1

13

样例 #2

样例输入 #2

见选手目录下的 potion/potion2.in。

样例输出 #2

见选手目录下的 potion/potion2.ans。

样例 #3

样例输入 #3

见选手目录下的 potion/potion3.in。

样例输出 #3

见选手目录下的 potion/potion3.ans。

提示

样例1解释 ：

一种最优的方案是购买 1 瓶第 1 种药水和 2 瓶第 2 种药水。使用第 1 种药水的数量为奇数，使用第 2 种药水的数量为偶数，得到的法力值为 (1 × 1 + 2) + (2 × 3 + 4) = 13。

样例2提示 ： 该样例满足测试点 6 的限制。

样例3提示 ： 该样例满足测试点 10 的限制。

数据范围： 对于所有测试数据，保证： $1 ≤ n, m ≤ 5000 ，1 ≤ v_i ≤ m，0 ≤ w_i , a_i , b_i ≤ 10^5$。