CF1252J.Tiling Terrace

Talia has just bought an abandoned house in the outskirt of Jakarta. The house has a nice and long yard which can be represented as a one-dimensional grid containing $1 \times N$ cells. To beautify the house, Talia is going to build a terrace on the yard by tiling the cells. Each cell on the yard contains either soil (represented by the character '.') or rock (represented by the character '#'), and there are at most $50$ cells containing rocks.

Being a superstitious person, Talia wants to tile the terrace with mystical tiles that have the power to repel ghosts. There are three types of mystical 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 (".#.").

Each tile of Type-1, Type-2, and Type-3 has the power to repel $G_1$, $G_2$, and $G_3$ ghosts per day, respectively. There are also some mystical rules which must be followed for the power to be effective:

• There should be no overlapping tiles, i.e. each cell is covered by at most one tile.
• There should be at most $K$ tiles of Type-1, while there are no limitations for tiles of Type-2 and Type-3.

Talia is scared of ghosts, thus, the terrace (which is tiled by mystical tiles) should be able to repel as many ghosts as possible. Help Talia to find the maximum number of ghosts that can be repelled per day by the terrace. Note that Talia does not need to tile all the cells on the yard as long as the number of ghosts that can be repelled by the terrace is maximum.

塔莉娅刚刚在雅加达郊区买下了一栋废弃的房屋。这栋房屋拥有一片漂亮而狭长的庭院，可被建模为一个 $1 \times N$ 的一维网格。为了美化房屋，塔莉娅计划在庭院上铺设露台。庭院中每个格子要么是土壤（用字符 . 表示），要么是岩石（用字符 # 表示），且岩石格子至多有 $50$ 个。

作为一名迷信之人，塔莉娅打算使用具有驱鬼魔力的神秘地砖来铺设露台。共有三种类型的神秘地砖：

• 1型砖：覆盖 $1 \times 1$ 的单个格子，仅能铺设在土壤格子（.）上；
• 2型砖：覆盖 $1 \times 2$ 的两个连续格子，仅能铺设在两个连续的土壤格子（..）上；
• 3型砖：覆盖 $1 \times 3$ 的三个连续格子，仅能铺设在“土壤-岩石-土壤”模式的连续三格上（.#.）。

每块1型、2型和3型砖每日分别可驱散 $G_1$、$G_2$ 和 $G_3$ 只鬼魂。此外，为使魔力生效，还需遵守以下神秘规则：

• 地砖之间不得重叠，即每个格子至多被一块地砖覆盖；
• 1型砖的数量至多为 $K$ 块；而2型砖与3型砖的数量则无限制。

塔莉娅非常害怕鬼魂，因此她希望所铺设的露台（由神秘地砖构成）能实现每日驱散鬼魂数量的最大化。请帮助塔莉娅计算该露台每日最多可驱散多少只鬼魂。注意：塔莉娅无需铺设庭院中的所有格子，只要所选铺设方案能使驱鬼总数最大化即可。

Input begins with a line containing five integers: $N$ $K$ $G_1$ $G_2$ $G_3$ ($1 \le N \le 100\,000$; $0 \le K \le N$; $0 \le G_1, G_2, G_3 \le 1000$) representing the number of cells, the maximum number of tiles of Type-1, the number of ghosts repelled per day by a tile of Type-1, the number of ghosts repelled per day by a tile of Type-2, and the number of ghosts repelled by a tile of Type-3, respectively. The next line contains a string of $N$ characters representing the yard. Each character in the string is either '.' which represents a soil cell or '#' which represents a rock cell. There are at most $50$ rock cells.

输入的第一行包含五个整数：$N$ $K$ $G_1$ $G_2$ $G_3$（其中 $1 \le N \le 100\,000$；$0 \le K \le N$；$0 \le G_1, G_2, G_3 \le 1000$），分别表示单元格总数、Type-1 类地砖的最大可用数量、一块 Type-1 类地砖每天可驱散的幽灵数量、一块 Type-2 类地砖每天可驱散的幽灵数量，以及一块 Type-3 类地砖可驱散的幽灵数量。
下一行是一个长度为 $N$ 的字符串，表示庭院布局。该字符串中每个字符要么是 '.'（代表土壤单元格），要么是 '#'（代表岩石单元格）。岩石单元格总数至多为 $50$ 个。

Output in a line an integer representing the maximum number of ghosts that can be repelled per day.

在一行中输出一个整数，表示每天最多可以驱散的幽灵数量。

Explanation for the sample input/output #1

Let "A" be a tile of Type-1, "BB" be a tile of Type-2, and "CCC" be a tile of Type-3. The tiling "ACCCBB" in this case produces the maximum number of ghosts that can be repelled, i.e. $10 + 40 + 25 = 75$

Explanation for the sample input/output #2

This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling "BB#BBA" or "BB#ABB" produces the maximum number of ghosts that can be repelled, i.e. $100 + 100 + 10 = 210$. Observe that the third cell is left untiled.

Explanation for the sample input/output #3

The tiling "ACCCA.#", "ACCC.A#", or ".CCCAA#" produces the maximum number of ghosts that can be repelled, i.e. $30 + 100 + 30 = 160$. Observe that there is no way to tile the last cell.

样例输入/输出 #1 的说明

设 “A” 为类型-1 的砖块，“BB” 为类型-2 的砖块，“CCC” 为类型-3 的砖块。本例中，铺砖方案 “ACCCBB” 可驱散最多数量的幽灵，即 $10 + 40 + 25 = 75$。

样例输入/输出 #2 的说明

该样例输入与前一个样例输入具有相同的院子，但每个类型-2 砖块每天可驱散的幽灵数更多。铺砖方案 “BB#BBA” 或 “BB#ABB” 可驱散最多数量的幽灵，即 $100 + 100 + 10 = 210$。注意：第三个格子未铺设砖块。

样例输入/输出 #3 的说明

铺砖方案 “ACCCA.#”、“ACCC.A#” 或 “.CCCAA#” 可驱散最多数量的幽灵，即 $30 + 100 + 30 = 160$。注意：最后一个格子无法被铺设。