Условие

---

CODE@BURGAS 2024, ГРУПА A, ЗАДАЧА D. РАНИЦА
---
Имате раница с максимална вместимост W килограма и N предмета, всеки от които има определено тегло и стойност. Вашата задача е да изберете комбинация от предмети, така че общото тегло да не надвишава вместимостта на раницата, а общата стойност да е максимална.

Вход:
Първи ред съдържа две цяли числа: W - максималната вместимост на раницата и N - броят на предметите.
Следващите N реда съдържат двойки числа, където всяка двойка представлява теглото и стойността на предмет.

Изход: 
Връща максималната възможна стойност, която може да се постигне с предметите в раницата, без да се надвишава общото тегло.

Примерен вход:
50 3
10 60
20 100
30 120

Примерен изход: 
220

Обяснение: 
Максималната стойност се постига, когато се вземат първият и вторият предмет, които имат общо тегло 30 и обща стойност 160.