0/1 Knapsack Problem

Halloway Removals sends one van out per job. The van has a weight limit, and the warehouse holds a set of crates, each with its own weight and its own insured value. There is exactly one of each crate — a crate is either loaded or left behind, never split and never loaded twice. The dispatcher wants the most valuable load the van is allowed to carry.

Task: Print the highest total value that can be loaded without going over the weight limit.

Input

The first line holds the weight limit, a single integer from 0 to 10000. The second line holds the crate count n. Each of the next n lines holds two integers separated by a single space: that crate's weight, then its value. Both are positive. Further crate lines may follow those n — they are held back for a later van, and this job must ignore them.

Output

One line holding a single integer: the largest total value of a set of crates whose weights add up to at most the limit. Each crate may be used at most once. Print 0 when no crate fits.

Example:

Input:
50
3
10 60
20 100
30 120

Output:
220