Description

有1个容量为m的背包，现有n种物品，重量分别为w1,w2…wn，价值分别为v1,v….vn,若每种物品只有1件，求能放入的最大总价值。

Input Format

第一行：两个整数m(m<=200)和n(n<=30)
第2~n+1，每行两个整数wi和vi

Output Format

一个数据，最大总价值

10 4
2 1
3 3
4 5
7 9

12

Hint

无

Source

01背包 动态规划 信息学奥赛一本通 玄级