问题 5120 --天佑拯救文物

5120: 天佑拯救文物★★★★

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

题目描述

消防员天佑被派往一栋着火的房子里拯救文物,但是由于火实在太大了,他只能选择保存那些最有价值的文物。天佑需要 ti 秒来拯救 第 i 件文物,第 i 件文物将在 di 秒后被烧毁,如果 ti >= di 的话,意味着这件文物已经来不及被保存了。文物管理局给出了每一件文物的价值 pi 请你帮助天佑找出一组可以被拯救的文物序列,使这个序列内文物的总价值达到最大。天佑一次只能拯救一件文物,如果他选择先拯救文物 a ,再拯救文物 b 那么文物 a 将在 ta 秒内被保存,文物 b 将在 ta+tb 秒内被保存。

输入

第一行包含一个整数n(1<=n<=100),代表房子内的文物数量,接下来的n行每行包括3个整数 ti , di , pi

(1<=ti<=20,1<=di<=2000,1<=pi<=20)分别代表拯救第 i 项文物所需的时间,它被烧毁的时间以及它的价值。

输出

第一行输出被拯救文物的最大价值
样例输入
Copy
3
3 7 4
2 6 5
3 7 6
样例输出
Copy
11

提示

来源

[提交][状态]