CF1252J Tiling Terrace

Talia 在雅加达郊区新买了一栋废弃房子，这里有个漂亮而悠长的院子，可以用 $1 \times N$ 的一维网格来表示，其中一共有 $N$ 个单元格。为了让房子更美观，Talia 打算在院子里铺设瓷砖建造一个露台。院子里的每个单元格要么是土壤（用字符 '.' 表示），要么是岩石（用字符 '#' 表示），其中不超过 50 个单元格是岩石。 由于 Talia 相信迷信，她希望用有驱赶鬼魂能力的神秘瓷砖来装点露台。这些瓷砖有三种类型： - Type-1：覆盖 $1 \times 1$ 的单元格，只能放在土壤单元格上（"."）。 - Type-2：覆盖 $1 \times 2$ 的单元格，只能放在两个相邻的土壤单元格上（".."）。 - Type-3：覆盖 $1 \times 3$ 的单元格，只能放在相邻的土壤-岩石-土壤单元格上（".#."）。 每种类型的瓷砖都有其独特的驱鬼能力：Type-1 每天可以驱赶 $G_1$ 个鬼魂，Type-2 可以驱赶 $G_2$ 个，Type-3 可以驱赶 $G_3$ 个。此外，必须遵循以下规则以确保瓷砖的效果： 1. 瓷砖之间不能重叠，即每个单元格最多只能被一块瓷砖覆盖。 2. Type-1 瓷砖最多只能使用 $K$ 块，而 Type-2 和 Type-3 的使用数量没有限制。 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$，分别代表单元格的总数、Type-1 瓷砖的最大使用数量、每块 Type-1 瓷砖每天驱赶的鬼魂数量、每块 Type-2 瓷砖每天驱赶的鬼魂数量和每块 Type-3 瓷砖每天驱赶的鬼魂数量。接下来一行是长为 $N$ 的字符串，表示院子，每个字符要么是 '.' 表示土壤单元格，要么是 '#' 表示岩石单元格。岩石单元格最多有 50 个。

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

### 示例说明 1 设 "A" 为 Type-1 瓷砖，"BB" 为 Type-2 瓷砖，"CCC" 为 Type-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$ 个鬼魂。注意，最后一个单元格无法覆盖。 **本翻译由 AI 自动生成**