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

Бой состоит ровно из $N$ раундов. В каждом раунде следующие действия могут происходить в указанном порядке:

1. Босс может решить применить заклинание «Регенерация».
2. Вы можете решить применить заклинание «Яд», если у вас осталась мана.
3. Вы атакуете мечом, нанося $X$ урона.
4. Применяются все пассивные эффекты.

Есть два вида пассивных эффектов: регенерация и яд. Эффекты складываются, поэтому текущее состояние босса описывается тремя целыми числами: текущими очками здоровья ($hp$), числом уровней яда ($p$) и числом уровней регенерации ($r$). В начале боя нет ни яда, ни регенерации ($p=r=0$). Каждый уровень яда наносит $P$ урона, каждый уровень регенерации восстанавливает $R$ очков здоровья.

Заклинания имеют следующие эффекты:

«Регенерация»: увеличивает число уровней регенерации $r$ на $1$.

«Яд»: увеличивает число уровней яда $p$ на $1$. Если число уровней регенерации строго положительно ($r>0$), уменьшает его на $1$.

После раунда $hp$ уменьшается на $X+P\cdot p-R\cdot r$ (это значение может быть отрицательным, если босс лечится быстрее, чем вы наносите урон).

Для каждого раунда известно, применит ли босс «Регенерацию». У вас достаточно маны для $K$ применений «Яда» (необязательно тратить всю ману). Какой максимальный суммарный урон вы можете нанести боссу, то есть каково максимальное значение $hp_{start}-hp_{end}$? Считайте $hp_{start}=10^{1000}$, так что убить босса за $N$ раундов невозможно. Здоровье босса может превысить начальное значение (см. третий пример).

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

Первая строка содержит 5 целых чисел $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).

Вторая строка содержит двоичную строку длины $N$. Её $i$-й символ равен 1, если босс применяет «Регенерацию» в начале $i$-го раунда, и 0 иначе.

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

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

Примеры

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

2 1010 1 1 1
01

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

2021

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

3 2 1 1 1
001

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

8

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

10 1 10 40 1
1111111111

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

-40

Примечание

Рассмотрим первый пример. Мы можем применить «Яд» не более одного раза. Посмотрим, что будет, если применить его в первом раунде.

• В первом раунде применяем «Яд», поэтому к концу раунда будет 0 уровней регенерации и 1 уровень яда. Значит, $hp$ уменьшится на $X+P\cdot1-R\cdot0=1011$.

• В начале второго раунда босс применит «Регенерацию», поэтому к концу раунда будет 1 уровень регенерации и 1 уровень яда. Значит, $hp$ уменьшится на $X+P\cdot1-R\cdot1=1010$. Всего здоровье босса уменьшилось на $1011+1010=2021$.

Теперь посмотрим, что будет, если применить заклинание во втором раунде.

• В первом раунде заклинания не применяются, поэтому к концу раунда будет 0 уровней регенерации и 0 уровней яда. Значит, $hp$ уменьшится на $X+P\cdot0-R\cdot0=1010$.

• В начале второго раунда босс применит «Регенерацию», после чего будет 1 уровень регенерации. Затем мы применим «Яд», уменьшив число уровней регенерации на один. К концу раунда будет 0 уровней регенерации и 1 уровень яда. Значит, $hp$ уменьшится на $X+P\cdot1-R\cdot0=1011$. Всего здоровье босса вновь уменьшилось на $1010+1011=2021$.

Итак, независимо от момента применения «Яда» в этом примере, мы уменьшим здоровье на 2021.