B. Вор и спички
ограничение по времени на тест
0.5 second
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Вор пробрался на склад спичек и хочет украсть как можно больше спичек. На складе находится m контейнеров, в контейнере номер i находится ai коробок спичек, а в каждой коробке bi спичек. Все коробки имеют одинаковый размер. В рюкзак вора помещается ровно n коробок. Ваша задача найти наибольшее количество спичек, которое сможет унести вор. У него нет времени на перекладывание спичек между коробками, поэтому он просто выбирает не более n коробок так, чтобы суммарное число спичек в них было максимальным.

Входные данные

В первой строке входных данных находится число n (1 ≤ n ≤ 2·108) и число m (1 ≤ m ≤ 20). В i + 1 строке находится пара чисел ai и bi (1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10). Все числа во входных данных — целые.

Выходные данные

Выведите единственное число — ответ на задачу.

Примеры
Входные данные
7 3
5 10
2 5
3 6
Выходные данные
62
Входные данные
3 3
1 3
2 2
3 1
Выходные данные
7