Задача №115014. Выбор цветов для букета
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из \(n\) цветов.
Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов \(m\) различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка \(i\)-го вида в букете его супруга становится счастливее на \(a_i\), а от каждого следующего цветка такого вида она становится счастливее на \(b_i\). То есть, если в букете \(x_i > 0\) цветов вида \(i\), то от цветов этого вида жена Володи становится счастливее на \(a_i + (x_i - 1) \cdot b_i\).
Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета, набранного из доступных в магазине цветов.
В первой строке вводятся два целых числа \(n\) и \(m\) (\(1 \le n \le 10^9\), \(1 \le m \le 100\,000\)) — требуемое количество цветов в букете и количество доступных видов цветов.
Каждая из следующих \(m\) строк описывает \(i\)-й вид цветов и содержит два целых числа \(a_i\) и \(b_i\) (\(0 \le a_i, b_i \le 10^9\)) — увеличение счастья от первого цветка \(i\)-го вида и увеличение счастья от каждого последующего цветка этого вида.
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из \(n\) цветов.
В первом примере если взять 1 цветок первого типа и 3 цветка второго типа, то итоговое увеличение счастья от букета будет равно \(5 + 1 + 4 + 4 = 14\).
В втором примере если взять 2 цветка первого типа, 2 цветка второго типа и 1 цветок третьего типа, то итоговое увеличение счастья от букета будет равно \(5 + 2 + 4 + 2 + 3 = 16\).
В данной задаче \(25\) тестов, помимо тестов из условия, каждый из них оценивается в \(4\) балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n, m \le 7\) и \(a_i \le b_i\), наберут не менее \(8\) баллов.
Решения, корректно работающие при \(n, m \le 7\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(n, m \le 1000\) и \(a_i \le b_i\), наберут не менее \(24\) баллов.
Решения, корректно работающие при \(n, m \le 1000\), наберут не менее \(60\) баллов.
Решения, корректно работающие при \(a_i \le b_i\), наберут не менее \(40\) баллов.
4 3 5 0 1 4 2 2
14
5 3 5 2 4 2 3 1
16