Weighting Agent

По физкультуре у Вовочки тоже двойки. ПалПалыч готов простить их все, если Вовочка окажет спортзалу спонсорскую помощь – например, подарит какой-нибудь тренажёр.

Вовочка решил создать из подручных материалов простейший тренажёр: тяжёлый рюкзак, с которым можно выполнять приседания, качая мышцы ног. Рюкзак объёмом L литров у него есть. В качестве наполнителя Вовочка решил использовать имеющиеся в доме сыпучие вещества – крупы, стройматериалы, дедушкину дробь, наполнитель кошачьего лотка и т.п. Проинспектировав домашние запасы, Вовочка составил список из N имеющихся веществ, зафиксировав объём каждого V_i в л и массу M_i в кг.

Требуется заполнить рюкзак так, чтобы целая часть его веса в кг (P) была максимальной. Вещество можно использовать не полностью, а отсыпать часть имеющихся запасов.

Ввод: в первой строке натуральные числа L и N  10000, далее – N строк, в каждой 2 числа, разделённые пробелом – V и M для каждого вещества.

Вывод: единственное число – значение P.

Пример:

Ввод	Вывод
10 3 1 5 6 3 5 5	12