Rezolvare PBinfo #1755

Arpsod are în curtea sa N copaci foarte bătrâni, așezați în linie și numerotați de la 1 la N. Fiecare copac are o înălțime cunoscută, Hi. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni.

Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea 1, 2, 3, ... ,N iar cel de-al doilea în ordinea N, N-1, N-2, ... 1.

Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul 1 are un tarif de T1 pe metru iar muncitorul 2 un tarif de T2 pe metru. Dacă un muncitor a început să taie un copac, acesta îl va tăia integral. Din motive de protecție a muncii, muncitorilor nu le este permis să lucreze simultan. De aici apare următoarea pretenție: dacă după tăierea unui copac, muncitorul nu este înlocuit de colegul său, acesta va cere un cost suplimentar C pentru a rămâne să taie în continuare.

De exemplu, dacă avem 3 copaci: 1, 2, 3 și muncitorul 1 taie singur toți copacii, acesta va cere un cost suplimentar de 2 ori (pentru copacul 2 și copacul 3).

Cerința

Arpsod vă cere să determinați costul minim pe care îl poate plăti astfel încât toți cei N copaci să fie tăiați.

Date de intrare

Pe prima linie a fișierului democratie.in se va afla numărul natural N, reprezentând numărul de copaci.
Pe cea de-a doua linie vor exista N numere naturale nenule reprezentând înălțimile celor N copaci.
Pe cea de-a treia linie se vor afla două numere naturale T1 și T2 reprezentând tariful pe metru al muncitorului 1 respectiv al muncitorului 2.
Pe ultima linie se vor afla două numere naturale C1 și C2 reprezentând costul suplimentar cerut de muncitorul 1 respectiv muncitorul 2.

Date de ieșire

În fișierul democratie.out se va scrie, pe prima și singura linie din fișier, costul minim pe care Arpsod trebuie să-l plătească.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ T1, T2 ≤ 100
• 1 ≤ C1, C2 ≤ 10.000
• 1 ≤ Hi ≤ 100
• Se garantează că pentru 20% din teste 1 ≤ N ≤ 10
• Costul suplimentar este același indiferent de înălțimea copacului ce va fi tăiat.
• Este posibil ca un muncitor să taie singur toți copacii.
• Un muncitor va tăia complet un copac.
• Cam scumpă democrația asta!

Exemplu:

democratie.in

4
1 2 3 4
7 2
3 9

democratie.out

34

Explicație

Ordinea muncitorilor:
M2 -> M1 -> M2 -> M2
Costul: (2*4) + (7*1) + (2*3) + (2*2 + 9)