Задача B. Новогодняя ёлка-2 ≡

Автор:И. Олейников   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка также характеризуется двумя параметрами — максимальной массой игрушек, которую она может выдержать и красотой. Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M и K — соответственно максимальная масса игрушек на ёлке и количество купленных игрушек. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ K, M ≤ 100 1 ≤ vi, ki ≤ 100

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 2
1 2
2 2
 
4
0.035s 0.009s 15