Description

There are $n$ types of items, each with a weight and a value. Each type of item can be selected multiple times (unlimited quantity). Given a backpack with maximum capacity $M$, select items from the $n$ types (the same type can be selected multiple times) such that the total weight is less than or equal to $M$ and the total value is maximized.

Input Format

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

Output Format

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

Sample

10 4
2 1
3 3
4 5
7 9

max=12