题目描述

Yuan Ke is the roommate of the rookie, his brain capacity is limited, in playing the game with the rookie, the rookie found a small problem, he will have a corresponding amount of blood when eliminating any hero, and each hero has a corresponding its importance, when he eliminates the hero after, his brain capacity will increase, if he wants the maximum brain capacity, how he wants to kill the hero, please help him (even if the maximum his brain capacity is still so small OwO)

输入格式

Line 1 of the input file is two positive integers, N and m, separated by a space. (where N denotes the total hero and m is the size of Yuanke's brain capacity)

From line 2 to line m+1, line j gives the basic data of the item numbered j-1, with 2 non-negative integers v and p per line. (where v indicates the hero's blood and p indicates the hero's importance)

输出格式

The output file has only one positive integer (the data is guaranteed to result in no more than 10e8).

样例

1000 5 
800 2 
400 5 
300 5 
400 3 
200 2

3900

提示

By TOP

There are two groups of test samples, one small sample and one large sample