Du spielst ein Spiel und stehst vor dem Kampf gegen den geheimen Boss. In diesem Spiel greift dich der Boss nicht an, kann aber Regenerationszauber wirken.
Der Kampf besteht aus genau $N$ Runden. In jeder Runde können die folgenden Aktionen in dieser Reihenfolge stattfinden:
- Der Boss kann sich entscheiden, „Regeneration“ zu wirken.
- Du kannst „Gift“ wirken, falls du noch Mana hast.
- Du greifst mit einem Schwert an und verursachst $X$ Schaden.
- Alle passiven Effekte werden angewendet.
Es gibt zwei Arten passiver Effekte: Regeneration und Gift. Die Effekte sind stapelbar, daher lässt sich der aktuelle Zustand des Bosses durch drei ganze Zahlen beschreiben: aktuelle Lebenspunkte ($hp$), aktuelle Giftstapel ($p$) und aktuelle Regenerationsstapel ($r$). Zu Beginn gibt es weder Gift- noch Regenerationsstapel ($p=r=0$). Jeder Giftstapel verursacht $P$ Schaden, jeder Regenerationsstapel heilt $R$ Lebenspunkte.
Die Zauber haben folgende Effekte:
„Regeneration“: erhöht die Anzahl der Regenerationsstapel $r$ um $1$.
„Gift“: erhöht die Anzahl der Giftstapel $p$ um $1$. Ist die Anzahl der Regenerationsstapel positiv ($r>0$), wird sie um $1$ verringert.
Nach der Runde sinkt $hp$ um $X+P\cdot p-R\cdot r$ (dieser Wert kann negativ sein, wenn sich der Boss schneller heilt, als du Schaden verursachst).
Für jede Runde weißt du, ob der Boss „Regeneration“ wirken wird. Dein Mana reicht für $K$ Anwendungen von „Gift“ (du musst nicht alles verbrauchen). Wie groß ist der maximale Gesamtschaden am Boss, also der maximale Wert von $hp_{start}-hp_{end}$? Nimm $hp_{start}=10^{1000}$ an, sodass du den Boss in $N$ Runden nicht tatsächlich töten kannst. Seine Lebenspunkte können den Anfangswert überschreiten (siehe drittes Beispiel).
Eingabe
Die erste Zeile enthält 5 ganze Zahlen $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).
Die zweite Zeile enthält eine Binärzeichenkette der Länge $N$. Ihr $i$-tes Zeichen ist 1, wenn der Boss zu Beginn der $i$-ten Runde „Regeneration“ wirkt, andernfalls 0.
Ausgabe
Gib eine ganze Zahl aus: den maximalen Gesamtschaden, den du im Kampf verursachen kannst.
Beispiele
Eingabe 1
2 1010 1 1 1 01
Ausgabe 1
2021
Eingabe 2
3 2 1 1 1 001
Ausgabe 2
8
Eingabe 3
10 1 10 40 1 1111111111
Ausgabe 3
-40
Hinweis
Betrachten wir das erste Beispiel. Wir können „Gift“ höchstens einmal wirken. Sehen wir uns an, was bei einer Anwendung in der ersten Runde passiert.
In der ersten Runde wirken wir „Gift“, also gibt es am Ende 0 Regenerationsstapel und 1 Giftstapel. Daher sinkt $hp$ in dieser Runde um $X+P\cdot1-R\cdot0=1011$.
Zu Beginn der zweiten Runde wirkt der Boss „Regeneration“, also gibt es am Ende 1 Regenerationsstapel und 1 Giftstapel. Daher sinkt $hp$ um $X+P\cdot1-R\cdot1=1010$. Insgesamt sind die Lebenspunkte um $1011+1010=2021$ gesunken.
Betrachten wir nun eine Anwendung in der zweiten Runde.
In der ersten Runde werden keine Zauber gewirkt, also gibt es am Ende 0 Regenerationsstapel und 0 Giftstapel. Daher sinkt $hp$ um $X+P\cdot0-R\cdot0=1010$.
Zu Beginn der zweiten Runde wirkt der Boss „Regeneration“, sodass es danach 1 Regenerationsstapel gibt. Dann wirken wir „Gift“ und verringern die Anzahl der Regenerationsstapel um eins. Am Ende gibt es 0 Regenerationsstapel und 1 Giftstapel. Daher sinkt $hp$ um $X+P\cdot1-R\cdot0=1011$. Insgesamt sind die Lebenspunkte wieder um $1010+1011=2021$ gesunken.
Unabhängig davon, wann wir in diesem Beispiel „Gift“ wirken, verringern wir die Lebenspunkte also um 2021.