Description

A traveler has a backpack that can hold a maximum of $M$ kilograms. There are now $n$ items, with weights of $W_1, W_2, ..., W_n$ and values of $C_1, C_2, ..., C_n$, respectively. The goal is to determine the maximum total value the traveler can obtain.

Input Format

• The first line: two integers, $M$ (backpack capacity, $M \leq 200$) and $N$ (number of items, $N \leq 30$).
• Lines $2..N+1$: each line contains two integers $W_i$ and $C_i$, representing the weight and value of each item.

Output Format

A single line containing the maximum total value.

10 4
2 1
3 3
4 5
7 9

12