e-olymp
Змагання

Knapsack - Рюкзак

Рюкзак Алладина

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает - слишком большой вес рюкзак может просто не выдержать.

Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.

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

Будем считать, что в пещере имеются предметы n различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен w. Каждый предмет типа i имеет вес wi и стоимость vi (i = 1, 2, ..., n).

Входные данные

В первой строке содержится два натуральных числа w и n (1w250, 1n35) - максимальный вес предметов в рюкзаке и количество типов предметов. Следующие n строк содержат по два числа wi и vi (1wi250, 1vi250) - вес предмета типа i и его стоимость.

Выходные данные

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
10 2
5 10
6 19
Вихідні дані #1
20