diskete
Jednog lijepog sunčanog proljetnog dana u studenome Gustav je bio kod kuće i igrao se na kompjuteru. I ovo bi bio jedan posve običan dan da se Gustav nije malo previše zaigrao i uspio potrgati kompjuter. Sav izbezumljen, nazvao je svog prijetelja Marina da mu dođe pomoći spasiti njegove kodove od zaborava na strganom hard-disku, jer bi Gustav bez njih bio gotovo nitko i ništa. Marin je uskoro stigao, noseći sa sobom novo čudo tehnike: uređaj za spašavanje podataka sa uništenih hard-diskova(ili kraće, UZSPSUHDD), zajedno sa najnovijim modelima spremnika za podatke - MarinUltraDisketama(ili kraće, MUD(engl. mud = blato, neznam kakve to veze ima s ovim ali sam to morao spomenuti)) koje se odlikuju jednim giga mega ultra super svojstvom - mogu pohranjivati podatke, ali, to nije sve - što im je veći kapacitet, to više podataka na njih stane! No, da bi diskete funkcionirale normalno, moraju biti sasvim ispunjene podacima. I tako su oni odlučili presnimiti te Gustavove kodove na diskete. Ali nastao je novi problem: Gustav je imao jaaaako puno kodova te im je bilo potrebno jaaaako puno disketa, a budući da svaka disketa zauzima i neki prostor, i jaaaako velike police. A Gustav na zidu nema niti jednu policu. AAAAAAAAAA!
I tu sada nastupate vi. Potrebno je, umjesto Marina i Gustava kojima nejde matemetika, a još manje kodiranje, napraviti program koji će izračunati kolika je najmanja debljina svih disketa zajedno, kako bi Gustav znao koliko polica mora naručiti.
U prvom redu nalaze se dva broja, M i N, M je količina podataka na Gustavovom potrganom hard-disku izražena u MB, a N broj različitih vrsta disketa(Gustav i Marin mogu upotrijebiti bilo koji broj disketa svake vrste jer zbog specijalnih zasluga tvornici disketa na doživotnom raspolaganju imaju neograničenu količinu disketa). 1 < M < 100 000; 1 < N < 50.
U svakom od sljedećih N redova nalaze se po dva broja, Ci i Di, kapacitet i-te vrste disketa i debljina te vrste ( 1 <= Ci <= M, 1 <= Di <= 10000).
Potrebno je ispisati jedan broj, minimalnu debljinu svih iskorištenih disketa tako da svi Gustavovi kodovi budu sačuvani.
Ulaz:
100 10
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1
Izlaz:
10
Ulaz:
556 5
50 3
100 6
5 3
1 5
3 2
Izlaz:
37
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.