e-olymp
Competitions

Knapsack - Рюкзак

Aladdin's knapsack

Entering into the cave with treasures, our Aladdin did not take an old blackened lamp. He rushed to collect the gold coins and precious stones into his knapsack. He would, of course, take everything, but miracles do not happen - too much weight the knapsack can not hold.

Many times he laid out one thing and put others in their place, trying to raise the value of the jewels as high as possible.

Determine the maximum value of weight that Aladdin can put in his knapsack.

We will assume that in the cave there are objects of n different types, the number of objects of each type is not limited. The maximum weight that a knapsack can hold is w. Each item of type i has the weight wi and cost vi (i = 1, 2, ..., n).

Input

First line contains two integers w and n (1w250, 1n35) - the maximum possible weight of items in the knapsack and the number of types of items. Each of the next n lines contains two numbers wi and vi (1wi250, 1vi250) - the weight of item of type i and its cost.

Output

Print the maximum value of the loading, which weight does not exceed w.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
10 2
5 10
6 19
Output example #1
20