问题 21809 --逃亡的准备

21809: 逃亡的准备

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

题目描述

      每个人小时候都有自己的理想,但随着时间推移,渐渐的大多数人的理想变成了金钱.地位.面子... 于是大多数人 就变成了传说中的俗人。但我们的中中始终有自己的梦想,他要 环 游 世 界! 在20XX年X月X日中中开始环游世 界的准备工作.他开始准备自己的行囊
中中背包的容积为m ,中中有n样有用的东西 ,每样东西都有自己的价值Wi,和体积Vi ,每一样物品有Ni个 (Ni=0时表示有无限多个),于是乎我们的问题就是(你应该已经猜到了)...中中能带走的 东西的最大价值。
30%数据满足  1 <= m,n <=1000
100%数据满足  1 <=m,n <= 10000

输入

第 1 行: N,M--物品的种类和背包的容积 
第 2-N+1 行: Vi,Wi,Pi--三个整数:每个物品的体积.价值.个数

输出

单独的一行在给定的限制里可能得到的最大的价值。

样例输入

5 50 
1 1 50
2 4 3
48 49 1
1 51 1
3 3 3

样例输出

106

提示

来源

[提交][状态]