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)$. \InputFile 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. \OutputFile Print the maximum value of the loading, which weight does not exceed $s$.