C

C. Золотая лихорадка

Гуляя по одному из островов Алгосского архипелага, Гоша набрёл на пещеру, в которой лежат кучи золотого песка. К счастью, у Гоши есть с собой рюкзак грузоподъёмностью до M килограмм, поэтому он может унести с собой какое-то ограниченное количество золота.

Всего золотых куч n штук, и все они разные. В куче под номером i содержится m_i килограммов золотого песка, а стоимость одного килограмма — c_i алгосских франков.

Помогите Гоше наполнить рюкзак так, чтобы общая стоимость золотого песка в пересчёте на алгосские франки была максимальной.

Формат ввода

В первой строке задано целое число M — грузоподъёмность рюкзака Гоши (0 ≤ M ≤ 10⁸).

Во второй строке дано количество куч с золотым песком — целое число n (1 ≤ n ≤ 10⁵).

В каждой из следующих n строк описаны кучи: i-ая куча задаётся двумя целыми числами c_i и m_i, записанными через пробел (1 ≤ c_i ≤ 10⁷, 1 ≤ m_i ≤ 10⁸).

Формат вывода

Выведите единственное число —– максимальную сумму (в алгосских франках), которую Гоша сможет вынести из пещеры в своём рюкзаке.

Пример 1

10 3 8 1 2 10 4 5

36

Пример 2

10000 1 4 20

80