Programozás‎ > ‎Feladatok‎ > ‎

Olcsó tej

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