你正在玩一款遊戲，即將挑戰隱藏首領。在這款遊戲中，首領不會攻擊你，但會施放再生法術。

戰鬥恰好包含 $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$ 回合開始時施放「再生」，則第 $i$ 個字元為 1，否則為 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。