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

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

Багато разів він виймав одні речі і на їх місце клав інші, намагаючись збільшити вартість коштовностей.

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

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

Вхідні дані

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

Вихідні дані

Виведіть максимальну вартість товару, вага якого не перевищує $s$.

Приклади