Talia 刚在雅加达郊区买了一栋废弃的房子。这栋房子有一个漂亮且狭长的院子，可以表示为一个包含 $1 \times N$ 个单元格的一维网格。为了美化房子，Talia 打算通过铺设地砖在院子里建造一个露台。院子里的每个单元格要么是土壤（用字符 ‘.’ 表示），要么是岩石（用字符 ‘#’ 表示），其中包含岩石的单元格最多有 50 个。

作为一个迷信的人，Talia 想用具有驱鬼能力的神秘地砖来铺设露台。神秘地砖共有三种类型： 类型 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 地砖的使用数量没有限制。

Talia 很怕鬼，因此，她希望露台（由神秘地砖铺设而成）能够尽可能多地驱除鬼魂。请帮助 Talia 计算露台每天最多能驱除多少只鬼魂。注意，Talia 不需要铺满院子里的所有单元格，只要驱除的鬼魂总数达到最大即可。

输入格式

输入的第一行包含五个整数：$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$），分别代表单元格数量、类型 1 地砖的最大数量、类型 1 地砖每天驱除的鬼魂数量、类型 2 地砖每天驱除的鬼魂数量以及类型 3 地砖每天驱除的鬼魂数量。下一行包含一个长度为 $N$ 的字符串，表示院子。字符串中的每个字符要么是代表土壤单元格的 ‘.’，要么是代表岩石单元格的 ‘#’。岩石单元格最多有 50 个。

输出格式

输出一行一个整数，表示每天最多能驱除的鬼魂数量。

样例

样例输入 1

6 4 10 25 40
..#...

样例输出 1

75

说明 1

设 “A” 为类型 1 地砖，“BB” 为类型 2 地砖，“CCC” 为类型 3 地砖。在这种情况下，铺设方案 “ACCCBB” 产生的驱鬼数量最多，即 $10 + 40 + 25 = 75$。

样例输入 2

6 4 10 100 40
..#...

样例输出 2

210

说明 2

此样例与前一个样例的院子相同，但类型 2 地砖每天能驱除更多的鬼魂。铺设方案 “BB#BBA” 或 “BB#ABB” 产生的驱鬼数量最多，即 $100 + 100 + 10 = 210$。注意，第三个单元格未被铺设。

样例输入 3

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

样例输出 3

160

说明 3

铺设方案 “ACCCA.#”、“ACCC.A#” 或 “.CCCAA#” 产生的驱鬼数量最多，即 $30 + 100 + 30 = 160$。注意，最后一个单元格无法被铺设。