Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает --- слишком большой вес рюкзак может просто не выдержать. Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей. Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак. Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $s$. Каждый предмет типа $i$ имеет вес $w_i$ и стоимость $v_i\:(i = 1, 2, ..., n)$. \InputFile В первой строке содержится два натуральных числа $s$ и $n\:(1 \le s \le 250, 1 \le n \le 35)$ --- максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_i$ и $v_i\:(1 \le w_i \le 250, 1 \le v_i \le 250)$ --- вес предмета типа $i$ и его стоимость. \OutputFile Выведите максимальную стоимость груза, вес которого не превышает $s$.