Потрапивши до пещери зі сокарбом, наш Алладін не став брати стару почорнівшу лампу. Він кинувся збирати в свій рюкзак золоті монети і коштовні камінці. Він, взяв би, але чудес не буває — дуже велику вагу рюкзак может просто не витримати.
Багато разів він вймав одні речі і на їх місце клав інші, прагнувши збільшивти вартість коштовностей.
Потрібно визначити максимальну вартість вантажу, який Алладін зможе помістити в свой рюкзак.
Будемо вважати, що в пещері є предмети n різних типів, кількість предметів кожного типу необмежено. Максимальна вага, яку може витримати рюкзак, дорівнює s. Кожен предмет типу i має вагу wi і вартість vi(i=1,2,...,n).
В першому рядку записано два натуральних числа s і n(1≤s≤250,1≤n≤35) — максимальна вага предметів в рюкзаку і кількість типів предметів. Наступні n рядків містить гвпо два числа wi і vi(1≤wi≤250,1≤vi≤250) — вавга предмета типу i і його вартість.
Виведіть максимальну вартість товару, вага якого на перевищує s.