Aladdin's knapsack

Entering 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 cannot 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 $s$. Each item of type $i$ has the weight $w_i$ and cost $v_i(i=1,2,...,n)$.

Input

The first line contains two integers $s$ and $n(1\le s\le 250,1\le n\le 35)$ — 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 $w_i$ and $v_i(1\le w_i\le 250,1\le v_i\le 250)$ — the weight of item of type $i$ and its cost.

Output

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

Examples