题目描述

Talia 刚在雅加达郊区买下一栋废弃房屋。房屋有一个漂亮而狭长的院子，可以表示为一个包含 $N$ 个单元格的 $1\times N$ 一维网格。

为了美化房屋，Talia 打算在院子中铺设露台。

每个单元格中要么是泥土，用字符 . 表示；要么是岩石，用字符 # 表示。

保证岩石单元格数量不超过 $50$。

Talia 很迷信，她希望使用具有驱鬼能力的神秘砖块。砖块共有三种。

一号砖

覆盖 $1\times1$ 个单元格，只能放在一个泥土格 . 上。

每块一号砖每天能够驱赶 $G_1$ 只鬼。

二号砖

覆盖 $1\times2$ 个连续单元格，只能放在两个连续泥土格 .. 上。

每块二号砖每天能够驱赶 $G_2$ 只鬼。

三号砖

覆盖 $1\times3$ 个连续单元格，只能放在连续的“泥土—岩石—泥土”格：

.#.

每块三号砖每天能够驱赶 $G_3$ 只鬼。

为了让神秘力量生效，铺设方案必须满足：

1. 任意两个砖块不能重叠，即每个单元格至多被一块砖覆盖；
2. 一号砖最多使用 $K$ 块；
3. 二号砖和三号砖数量不限。

Talia 希望露台每天能够驱赶尽可能多的鬼。

不要求覆盖所有单元格，只需使总驱鬼能力最大。

请计算最大驱鬼数量。

输入格式

第一行包含五个整数：

N K G1 G2 G3

满足：

$$1\le N\le100\,000,$$ $$0\le K\le N,$$ $$0\le G_1,G_2,G_3\le1000.$$

第二行包含一个长度为 $N$ 的字符串，表示院子：

• . 表示泥土；
• # 表示岩石。

保证字符串中 # 的数量不超过 $50$。

输出格式

输出一个整数，表示露台每天能够驱赶的最大鬼数。

样例 1

输入

6 4 10 25 40
..#...

输出

75

说明

用 A 表示一号砖，用 BB 表示二号砖，用 CCC 表示三号砖。

铺设方式：

ACCCBB

收益为：

$$10+40+25=75.$$

样例 2

输入

6 4 10 100 40
..#...

输出

210

说明

可以采用：

BB#BBA

或：

BB#ABB

收益为：

$$100+100+10=210.$$

第三个单元格没有被砖覆盖。

样例 3

输入

7 2 30 10 100
..#...#

输出

160

说明

以下铺设方式均可达到最优：

ACCCA.#
ACCC.A#
.CCCAA#

收益为：

$$30+100+30=160.$$

最后一个单元格无法被覆盖。