Description

A traveler has a backpack that can hold at most $M$ kilograms. There are $n$ items available, with weights $W_1$, $W_2$, ..., $W_n$ and values $C_1$, $C_2$, ..., $C_n$. Find the maximum total value the traveler can obtain.

Input Format

The first line contains two integers: $M$ (backpack capacity, $M ≤ 200$) and $N$ (number of items, $N ≤ 30$).
Lines $2$ to $N+1$ each contain two integers $W$ and $C$, representing the weight and value of each item.

Output Format

A single line containing one number, representing the maximum total value.

Sample

10 4
2 1
3 3
4 5
7 9

12