#include <stdio.h>#include <iostream>#include <algorithm>#include <vector>#include <math.h>#include <map>#include <assert.h>#include <string.h>using namespace std;#define MP make_pair#define PB push_back#define REP(i,x) for (int i = 0;i < x;++i)long long f[1007][17];int next[1007],where[310];int weight[1007];char img[1007][31];int main(){ int n,m,A,B,K; while (cin >> n >> m >> A >> B >> K) { REP(i,n) scanf("%s",img[i]); REP(i,m+5) where[i] = n; for (int i = n-1;i >= 0;--i) { int position = -1; REP(j,m) if (img[i][j] != '.') { position = j; break; } assert(position != -1); if (img[i][position] == 'G') weight[i] = A; else weight[i] = 0; next[i] = where[position]; where[position] = i; } weight[n] = 0; next[n] = n; for (int i = 0;i <= n;++i) for (int j = 0;j <= K;++j) f[i][j] = 0x7f7f7f7f7f7fll; for (int i = 0;i <= K;++i) f[n][i] = f[n-1][i] = 0; for (int i = n-1;i >= 0;--i) for (int j = 0;j <= K;++j) { long long dont = f[i+1][j] + weight[i], non_repair = B + f[next[i]][j]; long long do_repair = j ? (B + f[i+1][j-1]) : -0x7f7f7f7f7f7fll; f[i][j] = min(dont,max(non_repair,do_repair)); } long long ans = 0x7f7f7f7f7f7fll; for (int j = K;j <= K;++j) { long long dont = f[0][j], non_repair = B + f[next[0]][j] + weight[next[0]]; long long do_repair = j ? (B + f[0][j-1]) : -0x7f7f7f7f7f7fll; ans = min(dont,max(non_repair,do_repair)); } cout << f[0][K] << endl; }}
