Sereja and the Arrangement of Numbers

题意翻译

给出 $m$ 个不同的数 $q_i$，并且每个数都有个对应的费用 $w_i$。 现在要在 $m$ 个数中选择一些数（每个数可使用任意多次，但是代价只会计算一次），用这些数组成一个长度为 $n$ 的数列，并且满足任意两个不同种类的数，至少有一次相邻。 问最大费用。

题目描述

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&lt;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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

5 2
1 2
2 3

输出样例 #1

5

输入样例 #2

100 3
1 2
2 1
3 1

输出样例 #2

4

输入样例 #3

1 2
1 1
2 100

输出样例 #3

100

说明

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