题目描述

有一个负重能力为m(m<=300)的背包和n(n<=100)种物品，第i种物品的价值为v[i]，重量为w[i]。在不超过背包负重能力的前提下选择若干个物品装入背包，使这些物品的价值之和最大。每种物品可以不选，也可以选择多个。假设每种物品都有足够的数量。

输入格式

第1行 m n 第2行到n+1行 每行两个数据，分别为每种物品的重量和价值，空格隔开。

输出格式

装入背包物品的最大价值

样例数据

input

12 4
2  1
3  3
4  5
7  9

output

max=15

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$