Talia 刚刚在雅加达郊区买了一栋废弃的房子。房子有一个又漂亮又长的院子,可以表示为包含 $$$1 \times N$$$ 个单元格的一维网格。为了美化房子,塔莉亚打算在院子里铺瓷砖,建造一个露台。院子里的每个单元格包含土壤(由字符“.”表示)或岩石(由字符“#”表示),并且最多有 $$$50$$$ 单元格包含岩石。
作为一个迷信的人,塔莉亚想用具有驱鬼能力的神秘瓷砖来铺露台。神秘瓷砖分为三种类型:
- Type-1:覆盖 $$$1 \times 1$$$ 单元格,并且只能放置在土壤单元格上(“.”)。
- Type-2:覆盖 $$$1 \times 2$$$ 单元格,并且只能放置在两个连续的土壤单元格上(“..”)。
- Type-3:覆盖 $$$1 \times 3$$$ 单元格,并且只能放置在连续的土壤-岩石-土壤单元格上(“.#.”)。
类型 1、类型 2 和类型 3 的每块瓷砖每天都有能力分别击退 $$$G_1$$$、$$$G_2$$$ 和 $$$G_3$$$ 鬼魂。为了让力量发挥作用,还必须遵循一些神秘的规则:
- 不应有重叠的图块,即每个单元格最多被一个图块覆盖。
- 类型 1 的图块最多应为 $$$K$$$,而类型 2 和类型 3 的图块没有限制。
塔莉亚害怕鬼,因此露台(铺有神秘瓷砖的)应该能够驱除尽可能多的鬼。帮助塔莉亚找出露台每天可以驱除鬼魂的最大数量。请注意,塔莉亚不需要平铺院子里的所有单元格,只要露台可以驱除的鬼魂数量最多即可。
输入
输入以包含五个整数的行开头: $$$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$$$ 岩石细胞。
输出
一行输出一个整数,代表每天可以驱除鬼魂的最大数量。
示例
输入 #1
6 4 10 25 40 ..#...
输出 #1
75
输入 #2
6 4 10 100 40 ..#...
输出 #2
210
输入 #3
7 2 30 10 100 ..#...#
输出 #3
160
注意
示例输入/输出#1 的说明
令“A”为类型1的图块,“BB”为类型2的图块,并且“CCC”为类型3的图块。在这种情况下,平铺“ACCCBB”会产生可驱除的最大鬼魂数量,即 $$$10 + 40 + 25 = 75$$$
示例输入/输出 #2 的说明
这个样本输入与之前的样本输入具有相同的码数,但是 Type-2 的每块瓷砖每天可以驱除更多的鬼魂。平铺“BB#BBA”或“BB#ABB”产生可驱除的鬼魂的最大数量,即$$$100 + 100 + 10 = 210$$$。观察第三个单元格是否处于闲置状态。
示例输入/输出 #3 的说明
平铺“ACCCA.#”、“ACCC.A#”或“.CCCAA#”产生可驱除的最大鬼魂数量,即 $$$30 + 100 + 30 = 160$$$。请注意,无法平铺最后一个单元格。