Назовем массив, состоящий из 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. Сережа поверил другу и согласился на договор, теперь ему стало интересно, а какую максимальную сумму денег он может заплатить.
Помогите Сереже, найдите максимальную сумму денег, которую Сережа может заплатить Диме.
Выходные данные
В единственную строку выведите максимальную сумму денег (в рублях), которую может потратить Сережа.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d
Примечание
В первом примере Сережа заплатит максимум 5 рублей, например, если Дима построит массив: [1, 2, 1, 2, 2]. Возможны и другие оптимальные массивы.
В третьем примере Сережа заплатит максимум 100 рублей, если Дима построит массив: [2].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 2
2 3
|
5
|
|
2
|
100 3
1 2
2 1
3 1
|
4
|
|
3
|
1 2
1 1
2 100
|
100
|