PID160 / 竞赛真理
题目描述

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

输入格式

第一行有两个正整数N和T,表示题目的总数以及 竞赛的时限(单位秒)。以下的N行,每行4个正整数W1i 、T1i 、W2i 、T2i ,

分别表示第i题:完全正确做出来的得分,完全正确做出来所花费的时间(单位秒),“骗”来的分数,“骗”分所花费的时间(单位秒)。其中,3 ≤N ≤30,2 ≤T ≤ 1080000,1 ≤ W1i 、W2i ≤ 30000,1 ≤ T1i 、T2i ≤ T。

输出格式

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

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论