Meal deals P51461


Statement
 

pdf   zip

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