0337. 4G Планшет

Имя входного файла: ipad.in
Имя выходного файла: ipad.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

После успешного выступления на очередном соревновании по программированию Геннадию подарили модный 4G Планшет и три месяца бесплатного интернет-трафика. В течении трёх месяцев наш герой использовал его для сёрфинга по Интернету. К сожалению, бесплатный доступ в сеть закончился и перед Геннадием встал вопрос о выборе нового оператора связи и интернет-тарифа.

Так как Геннадий до сих пор увлекается спортивным программированием, каждый его день занят прорешиванием очередного контеста. В связи с этим, он попросил своих знакомых в социальной сети помочь ему с выбором тарифа, с учётом того, что максимальный объем трафика от его планшета равен K МБ в месяц.

Друг Гены Пётр, провёл мониторинг операторов мобильной связи и предоставил полный список тарифов. Каждый тариф i он описал двумя числами: ai и bi, где ai – максимальный объем трафика в МБ в месяц, доступных клиенту, а bi – ежемесячная плата за тариф.

Вы увидели эти записи на страничке Геннадия в социальной сети и решили скорее ему помочь, написав программу, которая по предоставленным данным о тарифах выберет тот, который предоставляет не менее K МБ трафика в месяц, а из всех таких выберет тариф с минимальной стоимостью.

Формат входного файла

В первой строке входного файла вводится два целых числа K, N (1 ≤ K ≤ 1000, 1 ≤ N ≤ 100), где K – количество мегабайт трафика, которое Геннадий использует за месяц, N – количество тарифов.

В последующих N строках описываются тарифы двумя целыми числами ai, bi (1 ≤ ai, bi ≤ 2000), где ai, bi – максимальный объем трафика и стоимость тарифа i, соответственно.

Гарантируется, что всегда существует тариф j, у которого aj не меньше K.

Формат выходного файла

В выходной файл выведите одно целое число – минимальную ежемесячную плату, которую придется платить Геннадию.

Пример:

ipad.inipad.out
100 2 1000 100 150 99 99
10 3 5 10 10 15 20 20 15
5 5 5 10 5 9 3 5 6 8 10 2 2


Источник: Командный чемпионат школьников Карелии по программированию, 4 ноября 2012

Обсудить       Отправить решение



Версия для печати