Вам даны четыре целых числа \(n\), \(c_0\), \(c_1\) и \(h\) и бинарная строка \(s\) длины \(n\).
Бинарная строка — это строка, состоящая из символов \(0\) и \(1\).
Вы можете поменять любой символ строки \(s\) (но строка должна остаться бинарной после изменения). Вы должны заплатить \(h\) монет за каждое такое изменение.
Вы хотите купить строку после нескольких изменений (возможно, нуля). Чтобы купить строку, вы должны купить все ее символы. Чтобы купить символ \(0\), вы должны заплатить \(c_0\) монет, чтобы купить символ \(1\), вы должны заплатить \(c_1\) монет.
Найдите минимальное количество монет, которое нужно, чтобы купить строку.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество монет, нужное, чтобы купить строку.
Примечание
В первом наборе входных данных вы можете купить все символы и заплатить \(3\) монеты, потому что каждый из символов \(0\) и \(1\) стоит \(1\) монету.
Во втором наборе входных данных вы можете сначала поменять \(2\)-й и \(4\)-й символы строки с \(1\) на \(0\) и заплатить \(2\) монеты за это. Ваша строка станет равной \(00000\). После этого вы можете купить строку и заплатить \(5 \cdot 10 = 50\) монет за это. Общее число потраченных монет будет \(2 + 50 = 52\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00
|
3
52
5
10
16
22
|