题目描述

设有 $n$ 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 $m$，今从 $n$ 种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于 $m$，而价值的和为最大。

输入格式

第一行包含两个整数 $m, n$，分别表示背包容量和物品数量。

接下来 $n$ 行，每行包含两个整数 $w_i, c_i$，表示每个物品的重量和价值。

输出格式

输出一行，格式为 max=X，其中 $X$ 表示最大总价值。

10 4
2 1
3 3
4 5
7 9

max=12

数据规模与约定

对于全部的测试点，保证 $0 \leq m \leq 200$, $0 \leq n \leq 30$，并且对于每个物品，$w_i$ 和 $c_i$ 是非负整数。