Grasz w grę i zamierzasz walczyć z ukrytym bossem. W tej grze boss cię nie atakuje, ale może rzucać zaklęcia regeneracji.

Walka składa się z dokładnie $N$ rund. W każdej rundzie następujące działania mogą wystąpić w podanej kolejności:

1. Boss może zdecydować się rzucić zaklęcie „Regeneracja”.
2. Jeśli masz jeszcze manę, możesz zdecydować się rzucić zaklęcie „Trucizna”.
3. Atakujesz mieczem, zadając $X$ obrażeń.
4. Stosowane są wszystkie efekty pasywne.

Istnieją dwa rodzaje efektów pasywnych: regeneracja i trucizna. Efekty się kumulują, więc bieżący stan bossa można opisać trzema liczbami całkowitymi: aktualnym zdrowiem ($hp$), liczbą ładunków trucizny ($p$) i liczbą ładunków regeneracji ($r$). Na początku walki nie ma żadnych ładunków trucizny ani regeneracji ($p=r=0$). Każdy ładunek trucizny zadaje $P$ obrażeń, a każdy ładunek regeneracji przywraca $R$ punktów zdrowia.

Zaklęcia mają następujące efekty:

„Regeneracja”: zwiększa liczbę ładunków regeneracji $r$ o $1$.

„Trucizna”: zwiększa liczbę ładunków trucizny $p$ o $1$. Jeśli liczba ładunków regeneracji jest dodatnia ($r>0$), zmniejsza ją o $1$.

Po rundzie $hp$ zmniejsza się o $X+P\cdot p-R\cdot r$ (wartość ta może być ujemna, jeśli boss leczy się szybciej, niż zadajesz obrażenia).

Dla każdej rundy wiesz, czy boss rzuci „Regenerację”. Masz dość many, by rzucić „Truciznę” $K$ razy (nie musisz zużyć całej many). Jakie największe łączne obrażenia możesz zadać bossowi, czyli jaka jest maksymalna wartość $hp_{start}-hp_{end}$? Przyjmij $hp_{start}=10^{1000}$, więc nie możesz faktycznie zabić bossa w $N$ rund. Zdrowie bossa może przekroczyć początkową wartość (patrz trzeci przykład).

Wejście

Pierwszy wiersz zawiera 5 liczb całkowitych $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).

Drugi wiersz zawiera napis binarny długości $N$. Jego $i$-ty znak to 1, jeśli boss rzuca „Regenerację” na początku $i$-tej rundy, a w przeciwnym razie 0.

Wyjście

Wypisz jedną liczbę całkowitą — największe łączne obrażenia, które możesz zadać podczas walki.

Przykład

Wejście 1

2 1010 1 1 1
01

Wyjście 1

2021

Wejście 2

3 2 1 1 1
001

Wyjście 2

8

Wejście 3

10 1 10 40 1
1111111111

Wyjście 3

-40

Uwagi

Rozważmy pierwszy przykład. „Truciznę” możemy rzucić co najwyżej raz. Zobaczmy, co się stanie, jeśli rzucimy ją w pierwszej rundzie.

• W pierwszej rundzie rzucamy „Truciznę”, więc na jej końcu są 0 ładunków regeneracji i 1 ładunek trucizny. Zatem $hp$ zmniejszy się o $X+P\cdot1-R\cdot0=1011$.

• Na początku drugiej rundy boss rzuca „Regenerację”, więc na końcu są 1 ładunek regeneracji i 1 ładunek trucizny. W tej rundzie $hp$ zmniejsza się o $X+P\cdot1-R\cdot1=1010$. Łącznie zdrowie bossa spadło o $1011+1010=2021$.

Teraz zobaczmy, co się stanie, jeśli rzucimy to zaklęcie w drugiej rundzie.

• W pierwszej rundzie nie rzucamy zaklęć, więc na końcu są 0 ładunków regeneracji i 0 ładunków trucizny. Zatem $hp$ zmniejsza się o $X+P\cdot0-R\cdot0=1010$.

• Na początku drugiej rundy boss rzuca „Regenerację”, po czym jest 1 ładunek regeneracji. Następnie rzucamy „Truciznę”, zmniejszając liczbę ładunków regeneracji o jeden. Na końcu są więc 0 ładunków regeneracji i 1 ładunek trucizny. $hp$ zmniejsza się o $X+P\cdot1-R\cdot0=1011$. Łącznie zdrowie bossa znów spadło o $1010+1011=2021$.

Zatem w tym przykładzie niezależnie od chwili rzucenia „Trucizny” zmniejszymy zdrowie o 2021.