E. Реставрационное расстояние
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам нужно отреставрировать стену. Стена состоит из $$$N$$$ столбиков кирпичей, высота $$$i$$$-го столбика изначально равна $$$h_{i}$$$, высота измеряется количеством кирпичей. После реставрации все $$$N$$$ столбиков должны иметь одинаковую высоту.

Вам доступны следующие операции:

  • положить кирпич на верх одного из столбиков, стоимость этой операции равна $$$A$$$;
  • убрать кирпич с верха одного из непустых столбиков, стоимость этой операции равна $$$R$$$;
  • переложить один кирпич с верха одного из непустых столбиков на верх другого столбика, стоимость этой операции равна $$$M$$$.

Вы не можете создавать дополнительные столбики или игнорировать какие-то из существующих столбиков, даже если их высота стала равна $$$0$$$.

За какую минимальную суммарную стоимость возможно провести реставрацию, то есть сделать высоты всех столбиков равными?

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

В первой строке записаны четыре целых числа $$$N$$$, $$$A$$$, $$$R$$$, $$$M$$$ ($$$1 \le N \le 10^{5}$$$, $$$0 \le A, R, M \le 10^{4}$$$) — количество столбиков кирпичей в стене, а также стоимости доступных операций.

Во второй строке записаны $$$N$$$ целых чисел $$$h_{i}$$$ ($$$0 \le h_{i} \le 10^{9}$$$) — изначальные высоты столбиков.

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

Выведите одно целое число — минимальную суммарную стоимость реставрации стены.

Примеры
Входные данные
3 1 100 100
1 3 8
Выходные данные
12
Входные данные
3 100 1 100
1 3 8
Выходные данные
9
Входные данные
3 100 100 1
1 3 8
Выходные данные
4
Входные данные
5 1 2 4
5 5 3 6 5
Выходные данные
4
Входные данные
5 1 2 2
5 5 3 6 5
Выходные данные
3