Sereja and the Arrangement of Numbers

1000ms

262144K

Description:

Let's call an array consisting of n integer numbers a₁, a₂, ..., 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⁶, 1 ≤ m ≤ 10⁵). Next m lines contain pairs of integers. The i-th line contains numbers q_i, w_i (1 ≤ q_i, w_i ≤ 10⁵).

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.

Sample Input:

5 2
1 2
2 3

Sample Output:

Sample Input:

Sample Output:

Sample Input:

1 2
1 1
2 100

Sample Output:

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].

Informação

Provedor Codeforces

Código CF367C