Codeforces Round 215 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

graphs

greedy

sortings

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Sereja and the Arrangement of Numbers

time limit per test

1 secondmemory limit per test

256 megabytesinput

stdinoutput

stdoutLet's call an array consisting of *n* integer numbers *a*_{1}, *a*_{2}, ..., *a*_{n}, beautiful if it has the following property:

- consider all pairs of numbers
*x*,*y*(*x*≠*y*), such that number*x*occurs in the array*a*and number*y*occurs in the array*a*; - for each pair
*x*,*y*must exist some position*j*(1 ≤*j*<*n*), such that at least one of the two conditions are met, either*a*_{j}=*x*,*a*_{j + 1}=*y*, or*a*_{j}=*y*,*a*_{j + 1}=*x*.

Sereja wants to build a beautiful array *a*, consisting of *n* integers. But not everything is so easy, Sereja's friend Dima has *m* coupons, each contains two integers *q*_{i}, *w*_{i}. Coupon *i* costs *w*_{i} and allows you to use as many numbers *q*_{i} as you want when constructing the array *a*. Values *q*_{i} are distinct. Sereja has no coupons, so Dima and Sereja have made the following deal. Dima builds some beautiful array *a* of *n* elements. After that he takes *w*_{i} rubles from Sereja for each *q*_{i}, which occurs in the array *a*. Sereja believed his friend and agreed to the contract, and now he is wondering, what is the maximum amount of money he can pay.

Help Sereja, find the maximum amount of money he can pay to Dima.

Input

The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 2·10^{6}, 1 ≤ *m* ≤ 10^{5}). Next *m* lines contain pairs of integers. The *i*-th line contains numbers *q*_{i}, *w*_{i} (1 ≤ *q*_{i}, *w*_{i} ≤ 10^{5}).

It is guaranteed that all *q*_{i} are distinct.

Output

In a single line print maximum amount of money (in rubles) Sereja can pay.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5 2

1 2

2 3

Output

5

Input

100 3

1 2

2 1

3 1

Output

4

Input

1 2

1 1

2 100

Output

100

Note

In the first sample Sereja can pay 5 rubles, for example, if Dima constructs the following array: [1, 2, 1, 2, 2]. There are another optimal arrays for this test.

In the third sample Sereja can pay 100 rubles, if Dima constructs the following array: [2].

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/15/2024 03:19:26 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|