A13009 | Tiling Terrace

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.

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.