题目描述

有一个负重能力为$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}$