Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3282
Go Downstairs

Time Limit: 1 Second      Memory Limit: 32768 KB

Evil LCLL is walking downstairs in cute watashi's house! There are N levels of stairs. We can divide each level in M grids. There is exactly one stair in each level, that means exactly one grid in each level is a stair. The stair in each level is either one grid left or right to the last level's stair in the horizontal direction. When LCLL walks downstairs from the top level to the bottom level, he will follow the stairs, so the path is decided when the description of the stairs is given.

Watashi hid some gold in some of the stairs, so if LCLL step onto a stair that contains gold, he will steal it. The value of gold in each stair is A. In order to reduce the loss, each time LCLL steps onto a stair, watashi can choose to remove the stair. The cost of removing one stair is B. Once a stair with gold is removed, the gold in it is removed too so LCLL can not steal it. When the stair where LCLL is on is removed, LCLL will drop down vertically until he touches a stair or falls below the bottom stair. In the former case, he will go on walking downstairs. As the title, LCLL always walk downstairs only, and when he falls/walks below the bottom level, he stops.

Howerer, evil LCLL is so evil that he has a skill to rebuild the stair! Each time watashi removes a stair where LCLL stands on, he can choose to use the skill to rebuild the missing stair. Of course, if a stair with gold is removed by watashi, LCLL can not rebuild that gold :) Using this skill will cost LCLL much energy, so LCLL can use this skill at most K times.

LCLL wants to make watashi's lost as much as possible, while watashi what's to minimize it. They are both so clever and both take optimal action. Now given the decription of the the house, watashi wants to know what is the minimum lost.

Input

There are multiple cases (no more than 100).

The first line of each case is five integers: N M A B K (1 <= N <= 1000, 1 <= M <= 30, 1 <= A, B <= 10, 0 <= K <= 10)

Then N lines follow, each with M characters. '_' indicates a stair without gold, 'G' indicates a stair with gold, and '.' indicates an empty grid. There is exactly one '_' or 'G' in each line. And the position of each level's stair is one grid left or right to the last level's stair in the horizontal direction.

There is a blank line after each case.

Output

For each case, output hte minimum lost in a line.

Sample Input

5 5 5 5 0
_....
.G...
..G..
..._.
..G..

5 5 1 5 0
_....
.G...
..G..
..._.
..G..

5 5 5 5 1
_....
.G...
..G..
..._.
..G..

Sample Output

5
3
10

Hint

In the first case, watashi can remove the stair in the first level, and LCLL will directly fall below the bottom level. In the second case, the gold is not so valueable, so watashi will not remove any stair. In the last case, remove only the stair in the first level is not sufficient because LCLL can use his skill to repair it, so watashi needs to remove the stairs in first two levels.


Author: HANG, Hang
Source: ZOJ Monthly, December 2009
Submit    Status