あなたはゲームをプレイしており、隠しボスと戦おうとしています。このゲームではボスは攻撃しませんが、再生の呪文を唱えることができます。
戦闘はちょうど $N$ ラウンドからなり、各ラウンドでは次の動作がこの順序で行われます。
- ボスは「再生」の呪文を唱えるか選べます。
- 魔力が残っていれば、あなたは「毒」の呪文を唱えるか選べます。
- あなたは剣で攻撃し、$X$ のダメージを与えます。
- すべてのパッシブ効果が適用されます。
パッシブ効果には再生と毒の 2 種類があります。効果は重複するので、ボスの現在の状態は、現在の体力（$hp$）、毒の重複数（$p$）、再生の重複数（$r$）という 3 つの整数で表せます。戦闘開始時には毒も再生もありません（$p=r=0$）。毒 1 つにつき $P$ のダメージを与え、再生 1 つにつき体力が $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$ ラウンドで実際にボスを倒すことはできません。ボスの体力は初期値を超える場合があります（3 番目の例を参照）。
入力
入力の最初の行には 5 つの整数 $N,X,R,P,K$（$1\le N,X,R,P\le10^6$、$0\le K\le N$）が与えられます。
2 行目には長さ $N$ の二進文字列が与えられます。ボスが第 $i$ ラウンドの開始時に「再生」を唱えるなら第 $i$ 文字は 1、そうでなければ 0 です。
出力
戦闘中に与えられる合計ダメージの最大値を整数 1 つで出力してください。
入出力例
入力 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
注記
最初の例を考えます。「毒」は高々 1 回唱えられます。まず、最初のラウンドで唱えた場合を考えましょう。
最初のラウンドでは「毒」を唱えるので、終了時には再生が 0 個、毒が 1 個です。よって、このラウンドで $hp$ は $X+P\cdot1-R\cdot0=1011$ 減少します。
2 番目のラウンドの開始時にボスが「再生」を唱えるので、終了時には再生が 1 個、毒が 1 個です。$hp$ は $X+P\cdot1-R\cdot1=1010$ 減少します。合計でボスの体力は $1011+1010=2021$ 減少します。
次に、2 番目のラウンドで唱えた場合を考えましょう。
最初のラウンドでは呪文を唱えないので、終了時には再生も毒も 0 個です。よって、このラウンドで $hp$ は $X+P\cdot0-R\cdot0=1010$ 減少します。
2 番目のラウンドの開始時、ボスが「再生」を唱えて再生が 1 個になります。次に、あなたが「毒」を唱えて再生を 1 個減らします。終了時には再生が 0 個、毒が 1 個です。よって $hp$ は $X+P\cdot1-R\cdot0=1011$ 減少します。合計では再び $1010+1011=2021$ 減少します。
したがって、この例ではいつ「毒」を唱えても体力を 2021 減らせます。