A Tehetős Tej Termelő vállalat megveszi a gazdáktól a tejet, majd palackozza, és egy- és kétüveges csomagokban forgalmazza élelmiszerboltokban. Így aztán mindannyian finom müzlivel és tejjel indíthatjuk napjainkat.
A tej palackozása nagyon bonyolult üzlet, ahhoz, hogy nyereséget termeljen a cég, a lehető legalacsonyabban kell tartani a költségeket.
Segítsünk a Tehetős Tej Termelőknek abban, hogy a lehető legolcsóbban szerezhessék be a tejet. A TTT egy kiemelkedően tehetséges marketing osztályt működtet, akik pontosan meg tudják mondani, hogy egy nap hány üveg tejre lesz kereslet.
A vállalat több gazdával szerződött le, akiktől beszerzi a tejet. A gazdák akár különböző áron ajánlhatják terméküket, és mivel a tehenek kapacitása véges, meg tudják előre mondani, hogy egy nap legfeljebb hány liter tejet tudnak eladni.
A TTT minden nap minden gazdától egész liternyi tejet vesz (lehet, hogy semmit, lehet, hogy a teljes aznapi mennyiséget, vagy a kettő között bármennyi egész litert).
Adott:
- a TTT napi tej szükséglete;
- a tej literenkénti ára minden gazda esetében;
- a gazdák által eladott tej napi maximális mennyisége.
Megjegyzés: A gazdák napi termelésének összege biztosan elég a cég szükségleteinek fedezésére.
Feladat
Számoljuk ki, hogy mennyiért lehet a lehető legolcsóbban beszerezni a napi szükségletet.
Bemenet
- első sor: N (0 <= N <= 2,000,000) a napi tej szükséglet, M (0 <= M <= 5,000) a gazdák száma
- következő M sor: gazdánként az ár (0 <= Pi <= 1000), majd a maximális mennyiség (0 <= Ai <= 2000000)
Kimenet
A minimális költség, amivel beszerezhtő a szükséges mennyiségű tej.
Példa
| Bemenet |
Kimenet |
100 5
5 20
9 40
3 10
8 80
6 30
| 630
|
Tesztadatok
Címkék
A feladat forrása: USACO training material, Mixing Milk
Algoritmusok:
megoldás
2004-2016 BDG algoritmus szakkör