问题 22079 --小飞侠的游园方案

22079: 小飞侠的游园方案

时间限制: 1 Sec  内存限制: 128 MB
提交: 66  解决: 39
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

经过抽签选择,小智将军第一个进入考场。

菜虫:(身上散射出华贵的光芒)欢迎你,第一位挑战者!!
小智:……(走到菜虫身后,关灯)女王陛下,虽然我们国家现在很富裕,但也请您不要浪费电来用这么大功率的灯泡。

菜虫(汗):啊啊~~爱卿所言甚是~~那么,你的题目是……我们的情报组织探听到敌人的重要将领——小飞侠星期天会邀他的灵儿妹妹到公园去玩。公园里有很多娱乐项目,可并不是每一项他们都喜欢,所以他们对每一项都进行了喜欢度的评分。因为小飞侠也是一个了不起的角色,所以他一定会选择在有限时间内的最好的方案。现在要你做的就是找出在规定时间内他们选择哪几项不同的活动可以使其喜欢度之和达到最大,据此我们就可以知道他会在哪些地方出现,从而在那里派人看守了。

小智:(灯泡一亮)每个地方都派人看守不就行了?!
菜虫:……你是白痴吗?-_-##(都派人去看守的话我们会有多少桌三缺一?!)听好了,输入格式是第一行一个正整数 N1<=N<=100)表示总共的娱乐项目数;第二行一个正整数表示规定的时间t0<t<1000);下面有N行,其中第 i+2行有两个正整数fi0<=fi<=100)和ti0<ti<=100),分别表示对项目i喜欢度和它所耗费的时间。输出的时候在第一行输出最大的喜欢度之和。

输入

第一行一个正整数 N1<=N<=100)表示总共的娱乐项目数;第二行一个正整数表示规定的时间t0<t<1000);下面有N行,其中第 i+2行有两个正整数fi0<=fi<=100)和ti0<ti<=100),分别表示对项目i喜欢度和它所耗费的时间。

输出

第一行输出最大的喜欢度之和。

样例输入

3
5
1 2
5 5
4 3

样例输出

5

提示

来源

[提交][状态]