Te karabiny Łatwe

  _______     _  __               _     _               _           _
 |__   __|   | |/ /              | |   (_)             | |         | |
    | | ___  | ' / __ _ _ __ __ _| |__  _ _ __  _   _  | |     __ _| |___      _____
    | |/ _ \ |  < / _` | '__/ _` | '_ \| | '_ \| | | | | |    / _` | __\ \ /\ / / _ \
    | |  __/ | . \ (_| | | | (_| | |_) | | | | | |_| | | |___| (_| | |_ \ V  V /  __/
    |_|\___| |_|\_\__,_|_|  \__,_|_.__/|_|_| |_|\__, | |______\__,_|\__| \_/\_/ \___|
                                                 __/ |
                                                |___/
Musimy wysłać wojsko do zniszczenia armii wroga.
Podstawowym wyposażeniem są te karabiny(te na obrazku tym).
Jednak chcemy wydać jak najmniej pieniedzy, poniewaz wyszkolenie wojownika jest drogie.
W tym celu powołano najlepszego w okolicy analityka, czyli ciebie (Pan Tadeusz w ciebie wierzy)
Twoim zadaniem jest zminimalizowanie kosztu wyprawy, niestety nie jest to proste zadanie.
Koszt liczony jest w abstrakcyjny sposób. Dostajemy pozycje wrogich jednostek.
Jednostki owe przebywają na sektorach ułożonych na prostej linii
(szereg frontu jest usytuowany w zorganizowany sposób)
Kilka jednostek może przebywać w jednym sektorze.
Cena jest liczona w następujący sposób:
W każdym kroku wykonujemy jedną z 2 czynności
1. Dzielimy obecny sektor na 2 równe części i rozpatrujemy je odzielnie
2. Wysyłamy wojska na dany sektor
Jeżeli nie ma na danym sektorze wrogich jednostek to wysłamy tam Hobbita o cenie A.
W przeciwnym wypadku wyprawiamy Dunedaina, koszt wyprawy wyniesie
B * (dlugosc_sektora) * (liczba_wrogów_na_sektorze)
Musimy podać minimalny koszt wyprawy na wroga.

-----------------------------------------------------------------
W zadaniu wczytujemy 4 liczby całkowite dodatnie  N, K, A, B
N = liczba żołnierzy | N jest z przedziału ( 1 <= N <= 8 )
K = długość linii frontu wynosi 2^k  | K jest z przedziału ( 1 <= K <= 3 )
A = Cena Hobbita  | A jest z przedziału ( 1 <= A <= 10^4 )
B = Cena Dunedaina | B jest z przedziału ( 1 <= B <= 10^4 )
W następnym wierszu dostajemy dostajemy N liczb całowitych Xi która jest z przedziału (1<= Xi <=2^k) - pozycje wrogich jednostek
------------------------------------------------------------------

W jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczająca minimalną cenę wyprawy.

------------------------------------------------------------------

IN
2 2 1 2
1 3
OUT
6
------------------------------------------------------------------
Wyjaśnienie przykładu:
Pierwsza opcją jest wziecie calego przedziału (1 - 4) z cena 2*4*2 = 16.
Inną opcją jest podzielenie (1-2)  i  (3-4).
Dla sektora (1-2) możemy wyprawic wojsko za 2*2*1=4 lub podzielic na 2 cześci (1-1) i (2-2).
Przedział (1-1) wycennimy za 2*1*1=2 .Za przedział (2-2) zapłacimy 1 bo nie ma na nim wrogich wojsk.
Wiec przedział (1-2) możemy zapłacić 2+1=3 < 4
Analogicznie potrzebujemy dla przedziału (3-4) tez 3.
Wiec w sumie musimy wydać 6.