Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ