Fișierul intrare/ieșire	alpine.in, alpine.out	Sursă	ad-hoc
Autor	Cristian Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.07 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Alpine (clasele 10-12)

Un hacker își citește e-mailul cu programul Alpine. Pe lângă directorul Inbox, în care intră implicit mesajele primite, el și-a mai definit K directoare. Venit dintr-o vacanță, hackerul observă că i s-au adunat N mesaje în Inbox. După ce își citește poșta, hackerul dorește să salveze mesajul cu numărul i în directorul D_i, pentru 1 ≤ i ≤ N. El caută o metodă cât mai rapidă de a salva mesajele, cu următoarele reguli:

• Poziționează cursorul pe primul mesaj din Inbox.
• Se poate deplasa în jos (această operație este instantanee).
• Poate salva mesajul curent în directorul său potrivit. Această operație durează T₁ secunde.
• Poate adăuga mesajul curent la o selecție. Această operație durează T₂ secunde.
• Poate salva toate mesajele selectate în același director. Această operație durează T₃ secunde. După salvare, selecția este golită.

Date de intrare

Fișierul de intrare alpine.in conține pe prima linie numerele naturale N K T₁ T₂ T₃, cu semnificațiile de mai sus, despărțite prin spații. Pe a doua linie se află numerele naturale D₁, D₂, ..., D_N, despărțite prin spații.

Date de ieșire

În fișierul de ieșire alpine.out se va tipări costul total minim pentru a salva fiecare mesaj în directorul dorit.

Restricții

• 1 ≤ N ≤ 50.000
• 1 ≤ K ≤ 1.000
• 1 ≤ T₁, T₂, T₃ ≤ 10.000
• 1 ≤ D_i ≤ K pentru 1 ≤ i ≤ N

Exemplu

Explicație

...