Malac
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.
Feladat
Készíts programot, amely kiszámítja, hogy legkevesebb mekkora értéket tartalmaz a malacpersely!
Bemenet
A MALAC.BE bemeneti állomány első sorában van a perselyben lévő pénzek $S$ $(1\leq S\leq 10000 )$ összsúlya. A második sorban a pénzérmék $N$ $(1\leq N\leq 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).
Kimenet
A MALAC.KI állomány egyetlen sort tartalmazzon, azt a legkisebb értéket, amelyet a malacpersely biztosan tartalmaz!
Példa
| malac.be | malac.ki |
15
4
1 2
2 3
5 6
10 4 |
8 |
Tesztadatok
