- 描述
-
每次编程课的考试和测验前，张老师和杜老师都为了出题和选题绞尽脑汁。因为我们既希望让同学们得高分，增加对编程学习的兴趣，又必须考察大家对核心知识和算法的掌握情况。于是，这次考试前的选题工作，我们需要你的帮助。
我们已经准备好了n道候选题目，并且预估了每一道题目的得分和同学们解题需要花费的时间。在已知考试的总时长的情况，你的任务是写一个程序，告诉张老师和杜老师，应该从这些候选题目中选出哪些组成正式考题，使得同学们在考试总时间内能够得到的分数最高。
- 输入
- 第1行，包含2个整数n和m (1<=n<=1000, 1<=m<=10000) ，分别表示候选题目数和考试总时长（考试时长和每道题解题时间的单位都是分钟）。
第2行到第(n+1)行，每行2个整数，第(i+1)行的整数 pi, ti 分别表示解决第 i 道题得到的分数和所需花费的时间(1<=pi,ti<=10000)。 - 输出
- 一个整数，代表最高的分数。
- 样例输入
-
4 120 90 110 80 120 55 80 60 30
- 样例输出
-
115
- 提示
- 样例说明：
样例中有4道候选题目，考试总时长120分钟。如果选择第3、4题作为正式考试题，那么解题时间为80+30=110分钟（不超过120分钟），并且总分为55+60=115分。这也是所有方案中的最高得分，其他方案的得分都不如这个方案。
数据范围：
对于50%的数据，n<=20；
对于全部数据，n<=1000，1<=m,pi,ti<=10000；
