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 Gi 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.
Cerinţă
Scrieţi un program care determină costul total minim pentru ca staţia să îşi servească clienţii în cele N zile şi întreaga cantitate de gaz să fie consumată la sfârşitul celei de a N-a zi.
Date de intrare
Prima linie a fişierului de intrare gaz.in conţine 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 G1 G2 ... GN, 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.
Date de ieşire
Fişierul de ieşire gaz.out va conţine o singură linie pe care se va scrie costul total minim cerut.
Restricţii
• 1 ≤ N ≤ 2 000
• 1 ≤ L, Gi ≤ 1 000, i=1, 2, ... N
• 1 ≤ P, D, C ≤ 5 000
• Pentru 80% din teste vom avea N ≤ 100.
Exemple
gaz.in
gaz.out
Explicaţii
5 3 1 1
5 3 2 4 5 1
22
O planificare optimă este cea descrisă în continuare.
În dimineaţa primei zile se comandă 5 litri de gaz şi se depozitează în rezervorul propriu. La sfârşitul zilei se livrează 3 litri. Costul primei zilei este 5+3=8. Pe timpul nopţii vor rămâne 2 litri în rezervorul propriu, fără costuri suplimentare.
În a doua zi staţia nu se aprovizionează, dar livrează 2 litri de gaz. Costul acestei zile este 0.
În dimineaţa celei de a treia zi se comandă 10 litri de gaz, depozitându-se câte 5 litri în fiecare din cele două rezervoare. Seara se livrează 4 litri din rezervorul închiriat. În rezervorul propriu rămân pe timpul nopţii 5 litri de gaz, iar în rezervorul închiriat încă un litru pentru care se va plăti un dolar. La costul total se va aduna 10+3+1=14 dolari.
În dimineaţa zilei a patra staţia nu se aprovizionează, dar seara livrează 5 litri de gaz, unul din rezervorul închiriat şi 4 din rezervorul propriu. În timpul nopţii nu vor fi costuri suplimentare de depozitare.
În ultima zi se va livra ultimul litru de gaz din rezervorul propriu.
Costul total este: 8+14=22.