Mohó Marci malacperselyben gyűjti pénzét. Csak fémpénzeket rakott a perselybe, de nem jegyezte fel, hogy milyeneket. Felírta azonban az üres persely súlyát, így meg tudja állapítani a perselyben lévő pénzek összsúlyát. Ismeri továbbá az egyes pénzérmék egyedi súlyát és értékét. Szeretné kiszámítani, hogy mennyi az a legkisebb érték, amelyet a perselye biztosan tartalmaz. 

Készíts programot, amely kiszámítja, hogy legkevesebb mekkora értéket tartalmaz a malacpersely! 

A MALAC.BE bemeneti állomány első sorában van a perselyben lévő pénzek S (1<=S<=10000) összsúlya. A második sorban a pénzérmék N (1<=N<=100) száma található. A további N sor mindegyike két pozitív egész számot tartalmaz egy szóközzel elválasztva. Az első szám egy pénzérme értéke (nem nagyobb, mint 200), a második szám pedig a pénzérme súlya (nem nagyobb, mint 1000). 

A MALAC.KI állomány egyetlen sort tartalmazzon, azt a legkisebb értéket, amelyet a malacpersely biztosan tartalmaz! 

MALAC.BE	MALAC.KI
15 4 1 2 2 3 5 6  10 4	8

A feladat forrása: NTOITV 2000, 11-13. évfolyam,  2. forduló 

Algoritmusok: dinamikus programozás