Codeforces Round 215 (Div. 1) |
---|
Закончено |
Назовем массив, состоящий из n целых чисел a1, a2, ..., an, красивым, если он обладает следующим свойством:
Сережа хочет построить красивый массив 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].
Название |
---|