题意

四只蛋仔叠成四层蛋仔塔，塔底端初始位于坐标 $0$。自下而上依次编号为 $A,B,C,D$，$D$ 为最顶端蛋仔。

赛道总长为 $l$，划分为 $l$ 段长度为 $1$ 的路段，第 $i$ 段连通坐标 $i-1$ 与坐标 $i$。 第 $i$ 段地形由字符 $S_i$ 决定，从 $i-1$ 走到 $i$ 耗时规则：

• 平地0：花费 $t_0$ 秒
• 泥坑1：花费 $t_1$ 秒
• 加速板2：花费 $t_2$ 秒

两种操作

1. 普通前进 当前位置为 $x$ 且 $x<l$ 时，可前进至 $x+1$，耗时由对应路段地形决定。

2. 超级弹射 若坐标 $x$ 处存在含有 $j$ 只蛋仔的塔（$j\ge2$），最下方蛋仔可将上方 $j-1$ 只蛋仔瞬间弹射至 $\min(l,x+d)$ 位置，该操作不耗费任何时间。 操作后原位置底端蛋仔消失，被弹射的 $j-1$ 只蛋仔组成新蛋仔塔，上下顺序保持不变。

求原本处于最顶端的蛋仔 $D$ 到达终点坐标 $l$ 的最少耗时。

输入格式

第一行输入两个正整数 $l,d$ 第二行输入三个正整数 $t_0,t_1,t_2$，满足 $t_2<t_0<t_1$ 第三行输入长度为 $l$ 的字符串 $S$，仅由0 1 2构成

输出格式

输出一个整数，代表到达终点的最小总耗时

Samples

10 2
10 20 5
0000000000

40

Limitation

1s, 1024KiB for each test case.