Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Monetos

Vienoje sendaikčių mugėje senų monetų pardavėjas surengė atrakcioną. Į pakabintą ant svarstyklių maišelį buvo pripilta įvairių valstybių įvairių laikotarpių monetų. Maišelyje galėjo būti vienodų monetų. Šalia buvo iškabinta lentelė su visų pardavėjo turimų monetų rūšių kilmės istorija, svoriu ir dabartine verte.

img

Dalyviai perskaitydavo informaciją apie monetas, pasižiūrėdavo maišelio svorį ir spėdavo maišelyje esančių monetų vertę. Tiksliausiai atspėjęs laimėdavo prizą.

Parašykite programą, kuri pagal maišelio svorį nustatytų mažiausią bei didžiausią galimą maišelio vertę, kai žinomi visų monetų rūšių svoriai ir vertės.

Skaičiuojant minimalią ir maksimalią vertes monetų rinkinio svoris turi tiksliai sutapti su maišelio svoriu. Laikykite, kad pardavėjas turėjo neribotą kiekį kiekvienos rūšies monetų.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas maišelio svoris S (1\\leS\\le1000) ir lentelėje aprašytų monetų rūšių skaičius M (1\\leM\\le500).

Likusiose M eilučių įrašyta po du tarpais atskirtus sveikuosius skaičius v_i ir s_i (1\\lev_i\\le10000,1\\les_i\\le1000,1\\lei\\leM), apibūdinančius atitinkamą monetos rūšį. Pirmasis iš jų žymi monetos vertę, o antrasis - svorį.

Rezultatai

Rezultatus - du tarpu atskirtus sveikuosius skaičius - įrašykite į pirmąją rezultatų failo eilutę. Pirmasis skaičius tai minimali galima maišelio vertė, antrasis - maksimali galima maišelio vertė.

Jei iš lentelėje išvardintų monetų rūšių negalima sudaryti maišelio svorio (taip galėjo nutikti, jei pvz. svarstyklės buvo netikslios), į rezultatų bylą išveskite minus vienetą (-1).

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
104 3
3 4
8 4
30 50
 
63 208
 Minimali vertė yra 63, ji gaunama paėmus vieną pirmą monetą ir dvi trečias monetas (1 * 3 + 2 * 30 = 63); Maksimali vertė yra 208. Ji gaunama paėmus 26 antras monetas.