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

Описание

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает – слишком большой вес рюкзак может просто не выдержать. Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей. Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак. Будем считать, что в пещере имеются предметы N различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен W. Каждый предмет типа i имеет вес wi и стоимость vi (i = 1, 2, . . . , N).

Формат входных данных

В первой строке входного файла содержится два натуральных числа W и N – максимальный вес предметов в рюкзаке и количество типов предметов (1 <= W <= 250, 1 <= N <= 35). Следующие N строк содержат по два числа wi и vi – вес предмета типа i и его стоимость (1 <= wi <= 250, 1 <= vi <= 250).

Формат выходных данных

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