Олимпиадный тренинг

Задача 38384. Выбор цветов для букета


Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из n цветов.

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на ai, а от каждого следующего цветка  
такого вида она становится счастливее на bi. То есть, если в букете xi > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на ai + (xi − 1) · bi.

Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета, набранного из доступных в магазине цветов.

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 109 , 1 ≤ m ≤ 100 000) — требуемое 
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа ai и bi (0 ≤ ai , bi ≤ 109 ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

Формат выходных данных
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из n цветов.
 
Примеры
Входные данные Выходные данные
1 4 3
5 0
1 4
2 2
14
2 5 3
5 2
4 2
3 1
16