0/1 Knapsack

Problem Background

Special for beginners, ^_^

Problem Description

A traveller has a backpack with a maximum capacity of $m$ kilograms. Now there are $n$ items, whose weights are $W_1, W_2, \dots, W_n$ and whose values are $C_1, C_2, \dots, C_n$. Each item can be taken at most once. What is the maximum total value the traveller can obtain?

Input Format

Line $1$: two integers, $M$ (backpack capacity, $M\le 200$) and $N$ (number of items, $N\le 30$).

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

Output Format

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

Sample Input

10 4
2  1
3  3
4  5
7  9

Sample Output

12

Constraints

1s, 1024KiB for each test case.