O staţie de gaz are un rezervor subteran în care poate depozita cel mult $L$ litri de gaz, dar există posibilitatea depozitării unei cantităţi suplimentare de gaz într-un rezervor închiriat de capacitate nelimitată pentru care se va plăti o taxă de $C$ dolari pentru fiecare litru de gaz depozitat de la o zi la alta. Pentru a-şi servi clienţii, staţia se aprovizionează cu gaz cel mult o dată pe zi, dimineaţa. Preţul unui litru de gaz este de $D$ dolari. Pentru fiecare aprovizionare trebuie plătită o taxă de $P$ dolari în plus faţă de costul gazului comandat. În aceste condiţii, comandarea unei cantităţi mari de gaz poate creşte costul depozitării.

Staţia de gaz se închide după $N$ zile. Aceasta livrează clienţilor săi $G{~i~}$ litri de gaz, din stocul său, la sfârşitul fiecărei zile i, unde $i=1,2,..,N$. Problema constă în a alege cantităţile de gaz ce vor fi comandate zilnic, astfel încât la sfârşitul celei de a $N$-a zi întreaga cantitate de pe stoc să fie consumată şi costul total să fie minim. Se consideră că rezervorul este iniţial gol.

Staţia de gaz se închide după $N$ zile. Aceasta livrează clienţilor săi $G{~i~}$ litri de gaz, din stocul său, la sfârşitul fiecărei zile i, unde $i = 1, 2,.., N$. Problema constă în a alege cantităţile de gaz ce vor fi comandate zilnic, astfel încât la sfârşitul celei de a $N$-a zi întreaga cantitate de pe stoc să fie consumată şi costul total să fie minim. Se consideră că rezervorul este iniţial gol.

h2. Cerinta

h2. Date de intrare

Pe prima linie a fişierului de intrare gaz.in apar patru numere naturale separate prin câte un spaţiu, $L P D C$, cu semnificaţia din enunţ. A doua linie conţine numerele naturale $N G{~1~} G{~2~} ... G{~N~}$ , separate prin câte un spaţiu, unde $N$ reprezintă numărul zilelor după care staţia va fi închisă şi $Gi$ cantitatea de gaz necesară zilei $i, i=1,2,..,N$.

Pe prima linie a fişierului de intrare gaz.in apar patru numere naturale separate prin câte un spaţiu, $L P D C$, cu semnificaţia din enunţ. A doua linie conţine numerele naturale $N G{~1~} G{~2~} ... G{~N~}$, separate prin câte un spaţiu, unde $N$ reprezintă numărul zilelor după care staţia va fi închisă şi $Gi$ cantitatea de gaz necesară zilei $i, i = 1, 2,.., N$.

h2. Date de ieşire