| Fişierul intrare/ieşire: | branza.in, branza.out | Sursă | preONI 2007 Runda Finala |
| Autor | Adrian Vladu | Adăugată de |  Adrian Vladu •azotlichid |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | branza.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.
