C. Сережа и расстановка чисел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив, состоящий из n целых чисел a1, a2, ..., an, красивым, если он обладает следующим свойством:

  • рассмотрим все пары чисел x, y (x ≠ y) такие, что число x встречается в массиве a, и число y встречается в массиве a;
  • для каждой пары x, y должна существовать некоторая позиция j (1 ≤ j < n) такая, что выполняется одно из двух: либо aj = x, aj + 1 = y, либо aj = y, aj + 1 = x.

Сережа хочет построить красивый массив a, состоящий из n целых чисел. Но не все так просто, у друга Сережи Димы есть m талонов, на каждом из которых написано два целых числа qi, wi. Талон i стоит wi рублей и позволяет использовать при построении массива a сколько угодно чисел qi. У Сережи никаких талонов нет, поэтому Дима с Сережей договорились следующим образом. Дима строит некоторый красивый массив a из n элементов. После чего он берет с Сережи wi рублей за каждое qi, которое встречается в массиве a. Сережа поверил другу и согласился на договор, теперь ему стало интересно, а какую максимальную сумму денег он может заплатить.

Помогите Сереже, найдите максимальную сумму денег, которую Сережа может заплатить Диме.

Входные данные

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 2·106, 1 ≤ m ≤ 105). Следующие m строк содержат пары целых чисел. В i-ой строке содержатся числа qi, wi (1 ≤ qi, wi ≤ 105).

Гарантируется, что все qi различны.

Выходные данные

В единственную строку выведите максимальную сумму денег (в рублях), которую может потратить Сережа.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d

Примеры
Входные данные
5 2
1 2
2 3
Выходные данные
5
Входные данные
100 3
1 2
2 1
3 1
Выходные данные
4
Входные данные
1 2
1 1
2 100
Выходные данные
100
Примечание

В первом примере Сережа заплатит максимум 5 рублей, например, если Дима построит массив: [1, 2, 1, 2, 2]. Возможны и другие оптимальные массивы.

В третьем примере Сережа заплатит максимум 100 рублей, если Дима построит массив: [2].