L. 4G Планшет

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

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

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

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

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

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

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

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

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

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

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

Пример:

ipad.in	ipad.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

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