B"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 x 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: Each tile of Type-1, Type-2, and Type-3 has the power to repel G_1 , G_2 , and G_3 ghosts per day, respectively. There are also some mystical rules which must be followed for the power to be effective: 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_1 G_2 G_3 ( 1 <= N <= 100 ,000 ; 0 <= K <= N ; 0 <= G_1, G_2, G_3 <= 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 "...