3474: 竞赛真理

竞赛真理

【问题描述】

小天天在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。按照上面的做题方法，有可能出现选择的那几题做完之后还有空的情况（时间有多余），但是这些时间又不足以完全解决一道题目，为了更充分的利用时间，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。

根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定的时间内获得最高的得分，

【文件输入】

第一行有两个正整数n和t，表示题目的总数以及竞赛的时限（单位秒）。以下的n行，每行４个正整数w1i  、t1i 、w2i  、t2i ，分别表示第i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。

其中，3≤n≤30，2≤t≤1080000，1≤ w1i 、w2i ≤30000，1≤t1i 、t2i≤t。

【文件输出】

直接把所能得到的最高分值输出到文件truth.out，文件只有一行（包括换行符）。

【样例输入一】

【样例输出一】

【样例输入二】

【样例输出二】