19164번 - 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 × 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 × 1 cell and can only be placed on a soil cell (“.”).
• Type-2: Covers 1 × 2 cells and can only be placed on two consecutive soil cells (“..”).
• Type-3: Covers 1 × 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 G1, G2, and G3 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.

Input begins with a line containing five integers: N K G₁ G₂ G₃ (1 ≤ N ≤ 100 000; 0 ≤ K ≤ N; 0 ≤ G₁, G₂, G₃ ≤ 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.