Закупка носков

В одной военной части было принято революционное решение перейти от портянок к носкам. По такому случаю прапорщику Недалекому было поручено закупить n пар носков. Однако предложенная прапорщиком смета не удовлетворила начальство, и прапорщику было предложено очень-очень быстро переделать ее так, чтобы затраты были минимально возможными. Помогите бедному прапорщику составить такую смету.

Изучение рынка показало, что всего существует m различных поставщиков, которые продают носки разными пачками и по разным ценам. Пачка, содержащая a_i пар носков, продается за b_i рублей.

Разрешено покупать любое количество пачек у одного поставщика. Разрешено покупать пачки у нескольких поставщиков.

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

В первой строке входного файла INPUT.TXT содержатся числа n и m (1 ≤ n ≤ 10000, 1 ≤ m ≤ 100). Далее идут m пар чисел a_i, b_i (1 ≤ a_i ≤ 10000, 1 ≤ b_i ≤ 10000).

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

Выведите в выходной файл OUTPUT.TXT минимальную сумму денег, которую нужно потратить на покупку n пар носок.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]