你正在玩一个游戏，并且准备挑战隐藏 Boss。在这个游戏中，Boss 不会攻击你，但他们会施放回复法术。

战斗恰好持续 $N$ 个回合，在每个回合中，按顺序发生以下事件：

1. Boss 可以选择施放“回复”（Regeneration）法术。
2. 如果你还有法力值，你可以选择施放“中毒”（Poison）法术。
3. 你用剑攻击，造成 $X$ 点伤害。
4. 应用所有被动效果。

被动效果有两种：回复和中毒。这些效果可以叠加，这意味着 Boss 的当前状态可以用三个整数来描述：当前生命值（$hp$）、当前中毒层数（$p$）和当前回复层数（$r$）。在战斗开始时，没有中毒层数和回复层数（$p = r = 0$）。每层中毒效果造成 $P$ 点伤害，每层回复效果恢复 $R$ 点生命值。

法术具有以下效果：

• “回复”：将回复层数 $r$ 增加 1。
• “中毒”：将中毒层数 $p$ 增加 1。如果回复层数严格大于 0（即 $r > 0$），则将 $r$ 减少 1。

在回合结束时，$hp$ 将减少 $X + P \cdot p - R \cdot r$（如果 Boss 的回复速度快于你造成伤害的速度，该值可以为负数）。

对于每个回合，你都预先知道 Boss 是否会施放“回复”。你有足够的法力值来施放最多 $K$ 次“中毒”法术（你不一定非要用完所有的法力值）。你能对 Boss 造成的最大总伤害是多少？换句话说，$hp_{start} - hp_{end}$ 的最大值是多少？假设 $hp_{start} = 10^{1000}$，因此你无法在 $N$ 个回合内真正击杀 Boss。Boss 的生命值可以超过初始值（参见第三个样例）。

输入格式

输入的第一行包含 5 个整数 $N, X, R, P, K$（$1 \le N, X, R, P \le 10^6$，$0 \le K \le N$）。

输入的第二行包含一个长度为 $N$ 的二进制字符串。如果 Boss 在第 $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 \cdot 1 - R \cdot 0 = 1011$。
• 在第二回合开始时，Boss 将施放“回复”法术，因此在第二回合结束时将有 1 层回复效果和 1 层中毒效果。因此，本回合 $hp$ 将减少 $X + P \cdot 1 - R \cdot 1 = 1010$。总的来说，Boss 的生命值减少了 $1011 + 1010 = 2021$。

现在我们来看看如果在第二回合施放这个法术会发生什么。

• 在第一回合中，没有施放任何法术，因此在该回合结束时将有 0 层回复效果和 0 层中毒效果。因此，本回合 $hp$ 将减少 $X + P \cdot 0 - R \cdot 0 = 1010$。
• 在第二回合开始时，Boss 将施放“回复”法术，之后将有 1 层回复效果。然后，我们施放“中毒”法术，将回复层数减少 1。因此，在第二回合结束时将有 0 层回复效果和 1 层中毒效果。因此，本回合 $hp$ 将减少 $X + P \cdot 1 - R \cdot 0 = 1011$。总的来说，Boss 的生命值再次减少了 $1010 + 1011 = 2021$。

因此，在这个样例中，无论我们在什么时候施放“中毒”法术，我们都将使 $hp$ 减少 2021。