Energija
Proizvodnja i optimalno upravljanje proizvodnjom energije je od velike važnosti za svako društvo. Procjenjuje se da će Bosna i Hercegovina za deset godina imati do 1000 različitih postrojenja za proizvodnju električne energije. Pored postojećih termo i hidro elektrana izgradiće se cijeli parkovi novih malih hidro i vjetro elektrana. Svaka od elektrana može raditi sa punom ali i sa svakom drugom manjom snagom većom od nula. Električna energija se teško skladišti pa je potrebno proizvesti tačno onoliko energija kolika je potražnja za nju.
Vaš zadatak je da napišete program koji će za datu potražnju za energijom u jednom danu i za datu listu elektrana sa njihovom maksimalnom proizvodnjom i i cijenom proizvodnje po jedinici naći najbolji (najjeftiniji plan proizvodnje).
Prva linija standardnog ulaza sadrži broj N ( 1 ≤ N ≤ 1000 ) koji označava ukupan broj elektrana. U sljedećem redu je ukupna potražnja za energijom. Nakon toga, u sljedećih N redova su data dva broja gdje u i-tom redu prvi broj označava moguću maksimalnu energiju elektrane a drugi broj je cijena proizvodnje po jedinici te energije. Svi brojevi su cijeli pozitivni brojevi manji od 10000000.
Standardni izlaz sadrži samo jednu liniju sa jednim brojem, minimalnom cijenom zadovoljavanja proizvodnje.
Input
5
21
5 4
7 3
8 5
4 5
1 6Output
86Input
3
13
2 1
7 3
8 4Output
39Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.