eolymp
bolt
Try our new interface for solving problems
Problems

Aladdin's knapsack

Aladdin's knapsack

Time limit 1 second
Memory limit 128 MiB

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 data

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 data

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

Examples

Input example #1
10 2
5 10
6 19
Output example #1
20