Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из $$$n$$$ цветов.
Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов $$$m$$$ различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка $$$i$$$-го вида в букете его супруга становится счастливее на $$$a_i$$$, а от каждого следующего цветка такого вида она становится счастливее на $$$b_i$$$. То есть, если в букете $$$x_i \gt 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$$$ цветов.
В данной задаче $$$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
В первом примере если взять 1 цветок первого типа и 3 цветка второго типа, то итоговое увеличение счастья от букета будет равно $$$5 + 1 + 4 + 4 = 14$$$.
В втором примере если взять 2 цветка первого типа, 2 цветка второго типа и 1 цветок третьего типа, то итоговое увеличение счастья от букета будет равно $$$5 + 2 + 4 + 2 + 3 = 16$$$.
