Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает — слишком большой вес рюкзак может просто не выдержать.
Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.
Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак.
Будем считать, что в пещере имеются предметы различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен . Каждый предмет типа имеет вес и стоимость .
В первой строке содержится два натуральных числа и — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие строк содержат по два числа и — вес предмета типа и его стоимость.
Выведите максимальную стоимость груза, вес которого не превышает .