PID95 / 多多看DVD(加强版)
题目描述

多多进幼儿园了,今天报名了。只有今晚可以好好放松一下了(以后上了学后会很忙)。她的叔叔决定给他买一些动画片DVD晚上看。可是爷爷规定他们只能在一定的时间段L看完。(因为叔叔还要搞NOIP不能太早陪多多看碟,而多多每天很早就困了所以只能在一定的时间段里看碟)。多多列出一张表要叔叔给她买N张DVD碟,大多都是多多爱看的动画片(福音战士,机器猫,火影忍者,樱桃小丸子……)。这N张碟编号为(1,2,3……N)。多多给每张碟都打了分Mi(Mi>0),打分越高的碟说明多多越爱看。每张碟有播放的时间Ti。多多想在今晚爷爷规定的时间里看的碟总分最高。(必须把要看的碟看完,也就是说一张碟不能只看一半)。显然叔叔在买碟是没必要把N张全买了,只要买要看的就OK了,这样节省资金啊。而且多多让叔叔惯的特别任性只要他看到有几张就一定会看完。

可是出现了一个奇怪的问题,买碟的地方只买给顾客M(M<N)张碟,不会多也不会少。这可让多多叔叔为难了。怎么可以在N张碟中只买M张而且在规定时间看完,而且使总价值最高呢?

聪明的你帮帮多多的叔叔吧。

数据范围 by RQ

对于100%的数据m<n<=100 l<=1000

输入格式

输入文件有三行

第一行:两个数空格隔开的正整数,N,M,L(分别表示叔叔给多多买的碟的数量,商店要买给叔叔的碟的数量,爷爷规定的看碟的时间段)。

第二行到第N行,每行两个数:T,M,给出多多列表中DVD碟的信息。

输出格式

单独输出一行,表示多多今晚看的碟的总分。

如果商店卖给叔叔的M张碟无法在爷爷规定的时间看完输出0;

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