problema/cascaval

Cascaval

mi-e foame!

== include(page="template/taskheader" task_id="cascaval") ==
 
O companie producatoare de cascaval (si alte branzeturi) doreste sa isi planifice productia pe urmatoarele $N$ luni. Pentru fiecare luna $i$, compania cunoaste cererea de cascaval $D{~i~}$, exprimata in kilograme. Se cunoaste, de asemenea, costul pentru a produce $Q$ {$(Q > 0)$} kilograme de cascaval in luna $i$, ca fiind egal cu $F{~i~} + C{~i~}*Q$ ({$F{~i~}$} reprezinta costurile fixe, iar $C{~i~}$ reprezinta costurile variabile). Costul pentru a produce $0$ kilograme de cascaval este $0$. Compania poate sa stocheze o parte din cantitatea de cascaval produsa intr-o anumita luna, pentru a o folosi pentru satisfacerea cererii dintr-o luna ulterioara. Se cunoaste costul stocarii unui kilogram de cascaval in fiecare luna $i$ (pana la inceputul lunii urmatoare), ca fiind $S{~i~}$. Compania doreste sa satisfaca integral cererea din fiecare luna, platind pentru aceasta un cost total cat mai mic. Costul total este egal cu suma costurilor de productie si a costurilor de stocare din fiecare din cele $N$ luni.
 
h2. Date de intrare
 
Prima linie a fisierului de intrare $cascaval.in$ contine numarul natural $N$, reprezentand numarul de luni. A $i$-a din urmatoarele $N$ linii contine $4$ numere intregi, $F{~i~}$, $C{~i~}$, $S{~i~}$, si $D{~i~}$, separate prin cate un spatiu, avand semnificatiile precizate in enunt.
 
h2. Date de iesire
 
In fisierul de iesire $cascaval.out$ veti afisa costul total minim pe care trebuie sa il plateasca compania pentru a satisface integral cererea de cascaval din fiecare luna.
 
h2. Restrictii
 
* $1 ≤ N ≤ 100 000$
* $0 ≤ F{~i~} ≤ 1 000 000 000$
* $0 ≤ C{~i~} ≤ 1 000 000$
* $0 ≤ S{~i~} ≤ 100$
* $0 ≤ D{~i~} ≤ 1000$
* Cascavalul poate fi stocat oricat de multe luni (nu se strica).
 
h2. Exemplu
 
table(example). |_. cascaval.in |_. cascaval.out |
|4
4 3 2 1
3 2 1 4
2 1 4 3
1 4 3 2
|32
|
 
== include(page="template/taskfooter" task_id="cascaval") ==
 
 
 
 

public

task: cascaval

2360