Вам нужно отреставрировать стену. Стена состоит из \(N\) столбиков кирпичей, высота \(i\)-го столбика изначально равна \(h_{i}\), высота измеряется количеством кирпичей. После реставрации все \(N\) столбиков должны иметь одинаковую высоту.
Вам доступны следующие операции:
- положить кирпич на верх одного из столбиков, стоимость этой операции равна \(A\);
- убрать кирпич с верха одного из непустых столбиков, стоимость этой операции равна \(R\);
- переложить один кирпич с верха одного из непустых столбиков на верх другого столбика, стоимость этой операции равна \(M\).
Вы не можете создавать дополнительные столбики или игнорировать какие-то из существующих столбиков, даже если их высота стала равна \(0\).
За какую минимальную суммарную стоимость возможно провести реставрацию, то есть сделать высоты всех столбиков равными?
Выходные данные
Выведите одно целое число — минимальную суммарную стоимость реставрации стены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 100 100
1 3 8
|
12
|
|
2
|
3 100 1 100
1 3 8
|
9
|
|
3
|
3 100 100 1
1 3 8
|
4
|
|
4
|
5 1 2 4
5 5 3 6 5
|
4
|
|
5
|
5 1 2 2
5 5 3 6 5
|
3
|