测试数据来自 system/1616

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　考试就是用分数来评价一个学生的，那么在考试中如何在规定的时间内得到更高的分数就成为关键问题，其实信息学竞赛中又何尝不是如此。

　　我们知道，平时的在考试中，其中出现的试题一定是我们学过的知识，也就是说，所有的试题只要给足够的时间，那么我们一定能够完全正确的做出来。然而考试不可能没有时间限制，因此我们在开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的简便方法随便做做，争取“骗”一点分数。

　　现在给出一张试卷上每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定的时间内获得最高的得分。

【输入格式】

　　第 \(1\) 行有两个正整数 \(N\) 和 \(T\)，表示题目的总数以及竞赛的时限（单位秒）；
　　以下的 \(N\) 行，每行 \(4\) 个正整数 \(W_{1,i} ,T_{1,i} ,W_{2,i} ,T_{2,i}\) ，分别表示第 \(i\) 题：完全正确做出来的得分，完全正确做出来所花费的时间（单位秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。

【输出格式】

　　只有一行一个整数，表示最高分数。

【输入输出样例】

　Input

4 10800
18 3600 3 1800
22 4000 12 3000
28 6000 10 3000
32 8000 24 6000

　Output

50

【数据说明】

　　对于 \(100\%\) 的数据 \(3≤N≤30\)，\(2≤T≤10^6\)，\(1 ≤ W_{1,i},W_{2,i}≤ 30000\)，\(1≤T_{1,i},T_{2,i}≤T\)。

【来源】

　　Mr.he