Fişierul intrare/ieşire:branza.in, branza.outSursăpreONI 2007 Runda Finala
AutorAdrian VladuAdăugată deazotlichidAdrian Vladu azotlichid
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Branza

Taranul s-a plictisit de munca pe camp si a decis sa isi intemeieze o afacere. In acest sens, si-a deschis o fabrica de branza. In urmatoarele N saptamani pretul branzei va fluctua in functie de cerere. Din fericire taranul cunoaste dinainte (nu se stie de unde) care vor fi preturile in saptamanile ce vor urma. El vrea sa isi minimizeze costurile si sa acopere cerinta de branza. Pentru fiecare saptamana el cunoaste costul C pentru a produce un kg de branza si cantitatea P care va fi cumparata. Taranul poate produce intr-o saptamana orice cantitate de branza. El poate depozita excesul de branza intr-un depozit, dar trebuie sa plateasca S unitati monetare pentru fiecare kg de branza depozitat timp de o saptamana. Branza poate fi depozitata maxim T saptamani inainte sa se strice. Ajutati taranul sa-si minimizeze costurile.

Date de intrare

De pe prima linie a fisierului de intrare branza.in se citesc trei numere intregi N, S si T cu semnificatiile de mai sus. De pe urmatoarele N linii se citesc cate doua numere intregi Ci si Pi, reprezentand costul pentru a fabrica un kg de branza in saptamana i, respectiv cantitatea care va fi cumparata in acea saptamana.

Date de iesire

Pe prima linie a fisierului de iesire branza.out se afla un singur numar intreg reprezentand costul minim necesar pentru ca taranul sa poata satisface cerinta de branza.

Restrictii

  • 1 ≤ N, T ≤ 100 000
  • 1 ≤ S ≤ 100
  • 1 ≤ Ci, Pi ≤ 10 000 000

Exemplu

branza.inbranza.out
5 10 3
12 1
21 2
27 4
45 5
52 3
488

Explicatie

In ziua 1 taranul produce 1 kg de branza cu costul 12*1 = 12.
In ziua 2 taranul produce 2 kg de branza cu costul 21*2 = 42.
In ziua 3 taranul produce 12 kg de branza cu costul 27*12 = 324.
In ziua 4 taranul nu produce branza, dar plateste taxa de depozitare pentru 8 kg, cu costul 8*10 = 80.
In ziua 5 taranul nu produce branza, dar plateste taxa de depozitare pentru 3 kg, cu costul 3*10 = 30.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content