问题 W: 背包问题

问题 W: 背包问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 85  解决: 58
[提交][状态][讨论版][命题人:]

题目描述

给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第 i 种食品的最多拥有Wi 公斤,其商品价值为Vi元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。

输入

输入只包括一个用例,第一行为两个正实数M,N,分别表示卡车载重量和食品种数,接下来N行,每行两个正实数,分别表示第i食品的重量和价值。


输出

输出一含一个数,即装入卡车的最大价值,要求只保留两位小数。

样例输入

5 3
2 9
3 11
1 5

样例输出

21.33

提示

[提交][状态]