Unbounded Knapsack

Background

Special for beginners, ^_^

Problem Description

There are $n$ kinds of items, each with a weight and a value. The quantity of each kind is unlimited. There is also a knapsack with maximum load $M$. Choose some items from the $n$ kinds (the same kind may be chosen multiple times) so that their total weight is at most $M$ and their total value is maximized.

Input Format

First line: two integers, $M$ (the knapsack capacity, $M \le 200$) and $N$ (the number of item kinds, $N \le 30$).

Lines $2 \dots N+1$: each line has two integers $W_i, C_i$, the weight and value of each item.

Output Format

A single line with one number: the maximum total value.

Sample Input 1

10 4
2 1
3 3
4 5
7 9

Sample Output 1

max=12

Constraints

1s, 1024KiB for each test case.