Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из n цветов.
Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на a
i, а от каждого следующего цветка
такого вида она становится счастливее на b
i. То есть, если в букете x
i > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на a
i + (x
i − 1) · b
i.
Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета, набранного из доступных в магазине цветов.
Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 10
9 , 1 ≤ m ≤ 100 000) — требуемое
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа a
i и b
i (0 ≤ a
i , b
i ≤ 10
9 ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.
Формат выходных данных
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из n цветов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 3
5 0
1 4
2 2 |
14 |
| 2 |
5 3
5 2
4 2
3 1 |
16 |