Tiling Terrace

Talia has just bought an abandoned house on the outskirts of Jakarta. The house has a long yard that can be represented as a one-dimensional grid of $1 \times N$ cells. To beautify the house, Talia will build a terrace on the yard by tiling its cells. Each cell contains either soil (.) or rock (#), and there are at most 50 rock cells.

Talia is afraid of ghosts, so she wants to use mystical tiles that repel them. There are three types of tiles:

• Type-1: covers $1 \times 1$ cell and can only be placed on a soil cell (.).
• Type-2: covers $1 \times 2$ cells and can only be placed on two consecutive soil cells (..).
• Type-3: covers $1 \times 3$ cells and can only be placed on consecutive soil-rock-soil cells (.#.).

A Type-1, Type-2, and Type-3 tile repels $G_1$, $G_2$, and $G_3$ ghosts per day, respectively. The following rules apply:

• Tiles may not overlap. Each cell is covered by at most one tile.
• At most $K$ Type-1 tiles may be used. Type-2 and Type-3 tiles have no limit.

Talia wants the terrace to repel as many ghosts as possible. She does not have to cover every cell as long as the number of ghosts repelled is maximal. Find that maximum number of ghosts repelled per day.

The first line contains five integers $N$, $K$, $G_1$, $G_2$, $G_3$ ($1 \le N \le 100000$, $0 \le K \le N$, $0 \le G_1, G_2, G_3 \le 1000$): the number of cells, the maximum number of Type-1 tiles, and the number of ghosts repelled per day by a Type-1, Type-2, and Type-3 tile, respectively. The next line contains a string of $N$ characters, each either . (soil) or # (rock). There are at most 50 rock cells.

Output one integer: the maximum number of ghosts that can be repelled per day.