L. 完全背包

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

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

第一行：两个整数， $M$ (背包容量， $M\le 200$ )和 $N$ (物品数量， $N\le 30$ )；

第 $2\dots N+1$ 行：每行二个整数 $w_i$ , $c_i$ ，表示每个物品的重量和价值。

输出仅一行。首先输出"max="（输出不含引号），后面输出一个数，表示最大总价值。（中间不含空格）

可参考样例的输出格式。

max=12


# Limitation

1s, 1024KiB for each test case.