During this week, the service of Jutge.org may be disrupted by major platform upgrades.

Edgar has become fond of the “meal deals” of England. For 3.5 pounds he can eat one first, one second, one third, …, and one n-th dish. Edgar wants to eat as many calories as possible, and he knows, for every dish of the deal, its type (between 1 and n) and its number of calories. Take into account that he can eat (at most) one dish of each type.

Input

Input consists of several cases, with only natural numbers.
Every case begins with the number of types of dishes n
and the number of different dishes d,
followed by d pairs t_{i} c_{i} with the type and the number of calories of each dish.
There is at least one dish for each type.
Assume 1 ≤ n ≤ 10^{4},
n ≤ d ≤ 10^{5},
1 ≤ t_{i} ≤ n,
and 1 ≤ c_{i} ≤ 10^{5}.

Output

For each meal deal, print the maximum number of calories that Edgar can eat.

Public test cases

**Input**

3 5 1 10 2 50 3 30 1 40 2 20 1 1 1 42 2 4 1 100000 1 100000 2 100000 1 100000

**Output**

120 42 200000

Information

- Author
- Edgar Moreno
- Language
- English
- Official solutions
- C++
- User solutions
- C++