Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 43%)

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
19 2
1 1
10 8
8

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483