# Meal deals P51461

Statement

thehtml

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 ti ‍ci with the type and the number of calories of each dish. There is at least one dish for each type. Assume 1 ≤ n ≤ 104, nd ≤ 105, 1 ≤ tin, and 1 ≤ ci ≤ 105.

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++