Ви граєте в гру та збираєтеся битися з таємним босом. У цій грі бос не атакує вас, але може застосовувати закляття регенерації.

Бій складається рівно з $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.