Потрапивши до пещери зі сокарбом, наш Алладін не став брати стару почорнівшу лампу. Він кинувся збирати в свій рюкзак золоті монети і коштовні камінці. Він, взяв би, але чудес не буває --- дуже велику вагу рюкзак может просто не витримати. Багато разів він вймав одні речі і на їх місце клав інші, прагнувши збільшивти вартість коштовностей. Потрібно визначити максимальну вартість вантажу, який Алладін зможе помістити в свой рюкзак. Будемо вважати, що в пещері є предмети $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$.