6. Vyrovnaná fotka

Jedného dňa prebehlo rokovanie rady starších Konglomerátu Sebecekých Podnikateľov. Prebralo sa veľa vecí. Na nejakých sa zhodnúť vedeli, na iných nevedeli. Zhodli sa však na jednom. Potrebujú spoločnú fotku zamestnancov konglomerátu (nie nutne všetkých). Samozrejme, má to byť reprezentatívna fotka. Konglomerát Sebeckých Podnikateľov má na ňu nemalé požiadavky tiež približné predstavy, ako by mala vyzerať. Bolo vybraných niekoľko reprezentatívnych zamestnancov, ktorí by mali byť na fotke, a tiež ich poradie. Teraz je ale medzi nejakými vedľa seba stojacimi zamestnancami veľmi veľký výškový rozdiel, a to by páni byrokrati radi opravili. Ako to už býva, nič nie je zadarmo.

Za nejakú sumu vie konglomerát zaplatiť ďalšiemu zamestancovi, a zamestnanec príde do radu na fotku na miesto, ktoré mu vyberú. V Konglomeráte je veľa zamestnancov všetkých možných rozmerov, teda je možné zohnať zamestnanca akejkoľvek výšky. Tiež je možné za určitú cenu poslať preč už vybraného zamestnanca, ktorého chcela mať rada starších na fotke, z radu na fotku preč. Za nejakú, stále trochu inú cenu, je dokonca možné poslať nejakého z už vybraných zamestancov na operáciu v najnovšej nemocnici Konglomerátu Sebeckých Podnikateľov, ktorá vie zmeniť výšku zamestnanca.

Pomôžte Konglomerátu Sebeckých Podnikateľov a zistite, ako najlacnejšie vedia rad na fotku upraviť tak, aby nebol medzi žiadnymi vedľa seba stojacimi zamestancami príliš veľký výškový rozdiel.

Úloha

Je zadaná postupnosť čísel \(A_1, A_2, ..., A_n\) dlhá \(n\) prvkov a čísla \(M, I, D\). Zadané sú aj povolené úpravy, z ktorých každá niečo stojí. Vašou úlohou je za čo najmenšiu cenu pomocou nich upraviť danú postupnosť tak, aby sa žiadne susediace prvky v upravenej postupnosti nelíšili o viac ako \(M\). Povolené úpravy a ich ceny sú nasledovné:

• Vloženie ľubovoľného celého čísla na ľubovoľné miesto v aktuálnej postupnosti za cenu \(I\).

• Odstránenie ľubovoľného prvku aktuálnej postupnosti \(A_i\) za cenu \(D\).

• Zmenena ľubovoľného prvku aktuálnej postupnosti \(A_i\) na \(x\) za cenu \(|A_i - x|\).

Vypíšte minimálnu cenu, za ktorú vieme postupnosť upraviť do požadovaného tvaru.

Formát vstupu

V prvom vstupu riadku sú celé čísla \(n, M, I, D\) (\(1 \leq n \leq 50\), \(0 \leq M, I, D \leq 10^9\)). V druhom riadku je medzerami oddelená postupnosť \(A_1, A_2, ..., A_n\) (\(0 \leq A_i \leq 50 000\)).

V jednotlivých sadách platia nasledujúce obmedzenia:

V prvej sade navyše platí, že \(max A_i \leq D\).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo - najmenšia cena, za ktorú vieme postupnosť upraviť do požadovaného tvaru.

Príklady

Input:

4 2 1 10
1 8 3 9

Output:

6

Môžeme najprv vložiť čísla \(3\) a \(5\) medzi 1 8, znížiť \(8\) na \(7\), zväčšiť \(3\) na \(5\) a vložiť \(7\) medzi posledné dva prvky aktuálnej postupnosti (teraz 5, 9). Takto dostaneme postupnosť 1 3 5 7 5 7 9, kde sa každé \(2\) susedné prvky líšia najviac o \(2\). Za úpravy sme zaplatili \(6\). Tento vstup sa môže objaviť aj v prvej sade, keďže \(max A_i \leq D, n \leq 5\) a \(max A_i \leq 10\)

Input:

3 2 1 2
1 10 5

Output:

3