gaz

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, \ldots, 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

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, \ldots G_N$, separate prin câte un spaţiu, unde $N$ reprezintă numărul zilelor după care staţia va fi închisă şi $G_i$ cantitatea de gaz necesară zilei $i$, $i=1,2, \ldots, N$.

Date de ieșire

În fişierul de ieşire gaz.out se va scrie pe prima linie costul total minim cerut.

Restricții și precizări

• $1 \leq N \leq 2 \ 000$
• $1 \leq L, G_i \leq 1 \ 000, i = \{ 1, 2, \ldots, N \}$
• $1 \leq P, D, C \leq 5 \ 000$
• Pentru $80\%$ din teste vom avea $N \leq 100$

Exemplu

gaz.in

5 3 1 1
5 3 2 4 5 1

gaz.out

22

Explicație

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$.