Задача №112693. У любой магии есть своя цена

Городок Сторибрук проклят Злой Королевой, и Эмме просто необходимо разрушить её чары. Для того чтобы спасти жителей маленького городка штата Мэн, ей необходимо преобразовать имеющееся заклинание, которое по странному стечению обстоятельств является математическим выражением, в эквивалент более сильного заклинания. Изначально у Эммы имеется выражение +\(x_1\)+\(x_2\)+...+\(x_n\). Для его преобразования доступны две операции:

1. Заменить в текущем выражении любой знак ‘+’ на ‘-’

2. Добавить в выражение пару из открывающейся и закрывающейся скобок. Открывающаяся скобка обязательно ставится сразу после знака ‘+’ или ‘-’, а закрывающаяся обязательно ставится сразу после переменной (и, разумеется, после соответствующей ей открывающейся).

Требуется получить выражение, эквивалентное \(⋄_1\) \(x_1\) \(⋄_2\) \(x_2\) \(⋄_3\) ... \(⋄_n\) \(x_n\);

где каждое \(⋄_i\) — это знак ‘+’ или ‘-’.

Выражения f(\(x_1\); \(x_2\); ... ; \(x_n\)) и g(\(x_1\); \(x_2\); ... ; \(x_n\)) называются эквивалентными, если f(\(x_1\); \(x_2\); ... ; \(x_n\)) = g(\(x_1\); \(x_2\); ... ; \(x_n\)) для любых(\(x_1\); \(x_2\); ... ; \(x_n\)), то есть они равны для любых возможных значений используемых переменных. С точки зрения предлагаемой задачи данное определение означает, что после раскрытия всех скобок каждая переменная встречается в обоих выражениях с одним и тем же знаком.

Эмма использует \(A\) единиц магии на выполнение каждой операции первого типа и \(B\) единиц магии на выполнение каждой операции второго типа. Помогите Эмме определить, какое минимальное количество единиц магии ей придётся использовать, чтобы преобразовать исходное выражение в эквивалентное требуемому.

Формат входного файла

В первой строке входных данных записано единственное целое число \(N\) (1 <= N <= \(10^6\)) — количество переменных в выражениях. Во второй строке записана строка длины \(N\), состоящая только из символов ‘+’ и ‘-’, \(i\)-й символ строки соответствует знаку \(⋄_i\). В третьей строке записаны два целых числа \(A\) и \(B\) (0 <= \(A\); \(B\) <= \(10^9\)), задающие стоимости операций

Формат выходного файла

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

Note

В первом примере Эмме выгодно сначала заменить первый ‘+’ на ‘-’, затратив одну единицу магии, а потом бесплатно поставить скобки. В результате у нее получится

-(\(x_1\) + \(x_2\) + \(x_3\)) = -\(x_1\) -\(x_2\) -\(x_3\)

Примеры
Входные данные
3
---
1 0
Выходные данные
1
Входные данные
7
--+++--
2 1
Выходные данные
6
Сдать: для сдачи задач необходимо войти в систему