C. Изобретательный щелчок
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Танос хочет уничтожить базу мстителей вместе с мстителями, которые там находятся.

Представим базу как массив, в каждой ячейке которой может находиться сколько угодно мстителей, но каждый мститель находится ровно в одной ячейке. Длина базы является точной степенью $$$2$$$. Танос хочет уничтожить базу, потратив минимум энергии. Он начинает со всей базы и за один шаг может сделать одно из следующего:

  • если текущая длина базы хотя бы $$$2$$$, разделить базу на $$$2$$$ равные половины и продолжить их уничтожать независимо, или
  • сжечь текущую базу. Если на ней нет мстителей, это отнимает $$$A$$$ единиц энергии, иначе это отнимает $$$B \cdot n_a \cdot l$$$ единиц энергии, где $$$n_a$$$ — число мстителей на этой базе, а $$$l$$$ — длина текущей базы.

Выведите минимальное число единиц энергии, которое должен затратить Танос, чтобы уничтожить всю базу.

Входные данные

Первая строка содержит четыре целых числа $$$n$$$, $$$k$$$, $$$A$$$ и $$$B$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq k \leq 10^5$$$, $$$1 \leq A,B \leq 10^4$$$), где $$$2^n$$$ — длина базы, $$$k$$$ — число мстителей, а $$$A$$$ и $$$B$$$ — константы, описанные в условие.

Вторая строка содержит $$$k$$$ целых чисел $$$a_{1}, a_{2}, a_{3}, \ldots, a_{k}$$$ ($$$1 \leq a_{i} \leq 2^n$$$), где $$$a_{i}$$$ — позиция очередного мстителя на базе.

Выходные данные

Выведите одно целое число — минимальное число единиц энергии, которое должен затратить Танос, чтобы уничтожить базу.

Примеры
Входные данные
2 2 1 2
1 3
Выходные данные
6
Входные данные
3 2 1 2
1 7
Выходные данные
8
Примечание

Рассмотрим первый пример.

Один из вариантов для Таноса — сжечь базу $$$1-4$$$ целиком, затратив $$$2 \cdot 2 \cdot 4 = 16$$$ единиц энергии.

В другом варианте он может разделить базу на две части $$$1-2$$$ и $$$3-4$$$.

Для базы $$$1-2$$$ он может либо сжечь ее целиком, затратив $$$2 \cdot 1 \cdot 2 = 4$$$ единиц энергии, либо разделить ее на $$$2$$$ части $$$1-1$$$ и $$$2-2$$$.

Для базы $$$1-1$$$ он может сжечь ее, затратив $$$2 \cdot 1 \cdot 1 = 2$$$ единиц энергии. Для базы $$$2-2$$$, он может сжечь ее, затратив $$$1$$$ единицу энергии, так как на ней нет мстителей. Поэтому он может уничтожить базу $$$1-2$$$ за $$$2 + 1 = 3$$$ единицы энергии, что меньше, чем $$$4$$$.

Аналогично, необходимо $$$3$$$ единицы энергии, чтобы уничтожить $$$3-4$$$. Итого, можно уничтожить всю базу за $$$6$$$ единиц энергии.