1695: 宝物筛选
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：7
题目描述
终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物……这下小FF可发财了，嘎嘎，但是这里面的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物，看来小FF只能含泪舍弃其中的一部分宝物了……，小FF队洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多见，他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作；小FF有一个最大载重为W的采集车，洞穴里总共有n种宝物，每种宝物的价值为v[i]，重量为w[i]，每种宝物有m[i]件，小FF希望在采集车不超过载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
输入
第一行为一个整数N和W,分别表示宝物种数和采集车的最大载重。
输出
输出仅一个整数ans，表示在采集车不超载的情况下收集的宝物的最大价值。
样例输入 复制
4
20
3 9 3
5
9 1
9
4 2
8
1 3
样例输出 复制
47提示
【数据范围】
对于30%的数据：n≤∑m[i]≤10∧4；0≤W≤10∧3。
对于100%的数据：n≤∑m[i]≤10∧5；0≤W≤4*10∧4；1≤n≤100。