如果一个由 n 个整数组成的数组 a1, a2, ..., an, beautiful 如果它具有以下属性:
- 考虑所有数字对 x, y (x ≠ y),使得数字 x 出现在数组 a 中,数字 y 出现在数组 a 中;
- 对于每对 x, y 必须存在某个位置 j (1 ≤ j < n),这样至少满足两个条件之一,aj = x, aj + 1 = y,或者aj = y, aj + 1 = x。
Sereja 想要构建一个漂亮的数组 a,由 n 个整数组成。但事情并不是那么容易,Sereja 的朋友 Dima 有 m 张优惠券,每张优惠券包含两个整数 qi,wi。优惠券 i 花费 wi 并允许您在构造数组 a 时使用任意数量的数字 qi 。值 qi 是不同的。 Sereja 没有优惠券,因此 Dima 和 Sereja 达成了以下协议。 Dima 构建了一些漂亮的 n 个元素数组 a。之后,他为每个 qi 从 Sereja 获取 wi 卢布,出现在数组 a 中。 Sereja相信了他的朋友并同意了这份合同,现在他想知道,他最多可以支付多少钱。
帮助Sereja,找到他可以支付给Dima 的最高金额。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 2·106, 1 ≤ m ≤ 105)。接下来的 m 行包含整数对。第 i 行包含数字 qi, wi (1 ≤ qi, wi ≤ 105)。
保证诸气分明。
输出
在单行中打印 Sereja 可以支付的最大金额(以卢布为单位)。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #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
注意
在第一个样本中,例如,如果 Dima 构建以下数组:[1, 2, 1, 2, 2],Sereja 可以支付 5 卢布。此测试还有另一个最佳阵列。
在第三个样本中,如果 Dima 构造以下数组:[2],Sereja 可以支付 100 卢布。