题目描述

$\text TENSHI$ 在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目骗”分，哪些不做），使能在限定的时间内获得最高的得分。

输入格式

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

输出格式

直接把所能得到的最高分值输出。

样例数据

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

50

3 7200
50 5400 10 900
50 7200 10 900
50 5400 10 900

70

数据规模与测试点

• 100%的数据，$3 ≤N ≤40，2 ≤T ≤ 1080000，1 ≤ W_{1i} 、W_{2i} ≤ 30000，1 ≤ T_{1i} 、T_{2i} ≤ T$。
• 其中 20%的数据，$3 ≤N ≤5，2 ≤T ≤ 1000，1 ≤ W_{1i} 、W_{2i} ≤ 300，1 ≤ T_{1i} 、T_{2i} ≤ T$。
• 另外20%的数据，$3 ≤N ≤10，2 ≤T ≤ 1080000，1 ≤ W_{1i} 、W_{2i} ≤ 30000，1 ≤ T_{1i} 、T_{2i} ≤ T$。