题目描述

题目描述

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是wi，它们的价值分别是vi元/公斤，求旅行者能获得最大总价值。

输入格式

第1行：两个整数，M背包容量（M<=1000）和N物品数量（N<=30）；

输出格式

一个数，表示最大总价值。

样例

样例 1

输入 # 1

100 3

40 2

50 3

70 3

输出 # 1

300