You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

      一个旅行者有一个最多能装m公斤的背包，现在有n件物品，它们的重量分别是w1,w2,...,wn,它们的价值分别为c1,c2,...cn。若每种物品只有1件，求旅行者能获得的最大总价值。

输入格式

   第一行：两个整数，m（背包容量，m<=200)和n（物品数量，n<=30)。
   第二~n+1行：每行两个整数wi,ci，表示每个物品的重量和价值。

输出格式

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

样例

10 4
2 1
3 3
4 5
7 9

12