#P1776. 宝物筛选
宝物筛选
题目描述
经过深入研究,小帅成功解开了千年之谜。在王室的宝物室中,他发现了无数价值连城的宝物。然而,宝物数量繁多,小帅的采集车无法容纳全部。无奈之下,他只能忍痛割爱,选取部分宝物。
在整理宝物的过程中,小帅发现每种宝物都有一件或多个。他初步估算了各类宝物的价值,并据此展开筛选。问题在于,小帅的最大载重为W,共有n种宝物,每种宝物的价值为vi,重量为wi,且每种宝物有mi件。小帅希望在不超过采集车载重的前提下,选取部分宝物,使它们的总体价值最大化。
输入格式
第一行为一个整数 和 ,分别表示宝物种数和采集车的最大载重。
接下来 行每行三个整数 。
输出格式
输出仅一个整数,表示在采集车不超载的情况下收集的宝物的最大价值。
4 20
3 9 3
5 9 1
9 4 2
8 1 3
47
提示
对于 的数据,,。
对于 的数据,,,。