问题 3650 --天佑领奖金

3650: 天佑领奖金★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 59  解决: 30
[提交][状态][命题人:]

题目描述

天佑惊喜地发现,自己的偶像beyond一举成名了!!!他打算马上从伦敦回中国去。不过问题来了:自己拿什么送给beyond呢?天佑思来想去,决定从侦探研究所领取一笔破案奖金。

这天,他无意中来到了贪心王国,贪心国王告诉他,这里的居民总喜欢不顾后果地把当前利益最大化,即优先选择奖金高的案件。这是当地的一种习俗。

贪心国王说:目前贪心王国有n件案子,如果天佑成功破案,则可领取每件案件金额不同的奖金。不过,天佑每件案件破案的时间也有长有短,而再过m天就是儿童节了,天佑要信守诺言,和妈妈一起去三亚旅游的。所以,SPR想请你帮他算算,天佑能拿多少奖金?

输入

第一行输入整数n<=50表示案件总数;

后面每行输入整数t<=20表示每个案件所需的破案时间,整数x<=100表示贪心国王给的奖金;

最后一行输入整数m<=200表示距离儿童节的时间;

输出

天佑最多能拿到的奖金数

样例输入
Copy
5
4 8
7 20
6 5
12 102
1 3
19
样例输出
Copy
122

提示

提示:如果没有捕获凶手,即案件没有全部完成,不能领奖金

样例解释:

先破解耗时12天的案件,再破解耗时7天的案件。

来源

[提交][状态]