eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

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

Giriş verilənləri

В первой строке содержится два натуральных числа 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 и его стоимость.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
10 2
5 10
6 19
Çıxış verilənləri #1
20