CF367C.Sereja and the Arrangement of Numbers

Let'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.

我们称一个由 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ 构成的数组是优美的，如果它满足如下性质：

• 考虑所有满足 $ x \ne y $ 的数对 $ (x, y) $，其中 $ x $ 和 $ y $ 均在数组 $ a $ 中出现；
• 对于每一对 $ (x, y) $，必须存在某个位置 $ j $（$ 1 \le j < n $），使得以下两个条件之一成立：$ a_j = x $ 且 $ a_{j+1} = y $，
  或 $ a_j = y $ 且 $ a_{j+1} = x $。

Sereja 想要构造一个长度为 $ n $ 的优美数组 $ a $。但事情并不简单：Sereja 的朋友 Dima 持有 $ m $ 张优惠券，每张优惠券 $ i $ 包含两个整数 $ q_i $、$ w_i $。使用第 $ i $ 张优惠券需花费 $ w_i $ 卢布，但它允许你在构造数组 $ a $ 时任意多次使用数字 $ q_i $。所有 $ q_i $ 的值互不相同。Sereja 自己没有优惠券，因此他与 Dima 达成了如下协议：Dima 构造某个长度为 $ n $ 的优美数组 $ a $；之后，他对数组 $ a $ 中每一个出现过的 $ q_i $ 向 Sereja 收取 $ w_i $ 卢布。Sereja 相信了他的朋友并同意了该协议，现在他想知道：他最多可能支付多少钱？

请帮助 Sereja，求出他最多需要支付给 Dima 的金额。

The first line contains two integers n and m (1 ≤ n ≤ 2·106, 1 ≤ m ≤ 105). Next m lines contain pairs of integers. The i-th line contains numbers q__i, w__i (1 ≤ q__i, w__i ≤ 105).

It is guaranteed that all q__i are distinct.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2\cdot10^6$，$1 \leq m \leq 10^5$）。接下来的 $m$ 行每行包含一对整数。第 $i$ 行包含数字 $q_i$ 和 $w_i$（$1 \leq q_i,\,w_i \leq 10^5$）。

保证所有的 $q_i$ 互不相同。

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.

在一行中输出 Sereja 能支付的最大金额（单位：卢布）。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

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

在第一个样例中，Sereja 可以支付 5 卢布，例如当 Dima 构造如下数组时：[1, 2, 1, 2, 2]。该测试点还存在其他最优数组。

在第三个样例中，Sereja 可以支付 100 卢布，当 Dima 构造如下数组时：[2]。