I. Gotta Go Fast
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Have you ever played Eggy Party? inf loves playing Eggy Party.

Four eggies are stacked into a four-story eggy tower, with the bottom initially at coordinate $$$0$$$. From bottom to top, they are sequentially labeled A, B, C, and D, where D is the topmost eggy.

The total length of the track is $$$l$$$, which consists of $$$l$$$ segments of length $$$1$$$. Segment $$$i$$$ connects coordinates $$$i-1$$$ and $$$i$$$ $$$(1 \le i \le l)$$$.

The terrain of the $$$i$$$-th segment is given by the character $$$S_i$$$. If the eggy tower walks from coordinate $$$i-1$$$ to coordinate $$$i$$$, the cost is:

  • Flat ground 0: $$$t_0$$$ seconds;
  • Mud pit 1: $$$t_1$$$ seconds;
  • Speed pad 2: $$$t_2$$$ seconds.

The eggy tower can perform two types of operations:

  • Normal Advance: If the current eggy tower is at coordinate $$$x \lt l$$$, it can advance forward to coordinate $$$x+1$$$. The time cost of this advance depends only on the terrain of segment $$$x+1$$$.
  • Super Start: If there is an eggy tower containing $$$j$$$ eggies at coordinate $$$x$$$ $$$(j \ge 2)$$$, the bottommost eggy can instantly throw the $$$j-1$$$ eggies above it to coordinate $$$\min(l, x+d)$$$, where $$$d$$$ is a given positive integer. This operation does not trigger any terrain time cost, i.e., it takes $$$0$$$ seconds. After the operation, the bottommost eggy at the original position is eliminated, leaving that position empty; a new eggy tower containing $$$j-1$$$ eggies is formed at coordinate $$$\min(l, x+d)$$$, and the vertical order of the remaining eggies stays the same.

Please compute the minimum time required for the initially topmost eggy D to reach the destination coordinate $$$l$$$.

Input

The first line contains two positive integers $$$l$$$ and $$$d$$$ ($$$1 \le d \lt l \le 2 \times 10^5$$$).

The second line contains three positive integers $$$t_0$$$, $$$t_1$$$, $$$t_2$$$ ($$$1 \le t_2 \lt t_0 \lt t_1 \le 10^9$$$).

The third line contains a string $$$S$$$ of length $$$l$$$, consisting only of the characters 0, 1, and 2.

Output

Output a single integer representing the minimum total time.

Examples
Input
10 2
10 20 5
0000000000
Output
40
Input
12 3
10 100 1
111000222000
Output
3
Input
10 2
10 100 1
2220110000
Output
13
Input
8 3
10 100 1
00000000
Output
0
Note

For Example 1: One optimal strategy is to consecutively trigger Super Start $$$3$$$ times to reach coordinate $$$6$$$, and then walk through the final $$$4$$$ flat ground segments. The total time cost is $$$4 \times 10 = 40$$$.

For Example 2: One optimal strategy is to first consecutively trigger Super Start twice to reach coordinate $$$6$$$, walk through $$$3$$$ speed pads to reach coordinate $$$9$$$, and finally trigger Super Start again to reach the destination. The total time cost is $$$1+1+1=3$$$.

For Example 3: One optimal strategy is to first walk through the first $$$3$$$ speed pads and $$$1$$$ flat ground segment to reach coordinate $$$4$$$, and then consecutively trigger Super Start $$$3$$$ times to reach the destination. The total time cost is $$$1+1+1+10=13$$$.

For Example 4: Consecutively trigger Super Start $$$3$$$ times. The coordinate changes as $$$0\to 3\to 6\to 8$$$ (the last time triggers the $$$\min (8, 6+3)$$$ limit). Walking is not needed throughout the process, and the total time cost is $$$0$$$.