题目描述

每种物品可以选择无限件，在容量为 M 的背包中最大化总价值。

输入格式

第一行 M,N，随后 N 行重量和价值。

输出格式

输出最大价值。

样例

10 4
2 3
3 4
4 5
7 10

15

数据范围

1≤M≤200，1≤N≤30，1≤物品重量、价值≤10000。