#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 2100000000
using namespace std;

int h, w, a, b, ans = inf;
string c[1005];
int memo[1005][1005] = {0};
bool ch[1005][1005] = {0};
pair<int, int> s, g;
int d[4] = {0, 1, 0, -1};
int ds[4] = {1, -1, -1, 1};

void solve();

int main() {
  cin >> h >> w >> a >> b;
  for(int i = 0; i < h; ++i) cin >> c[i];
  for(int i = 0; i < h; ++i)
    for(int j = 0; j < w; ++j) memo[i][j] = inf;
  for(int i = 0; i < h; ++i)
    for(int j = 0; j < w; ++j) {
      if(c[i][j] == 's') {
        s = {i, j};
        c[i][j] = '.';
        memo[i][j] = 0;
      }
      if(c[i][j] == 'g') {
        g = {i, j};
        c[i][j] = '.';
      }
    }
  for(int i = 0; i < h; ++i)
    for(int j = 0; j < w; ++j) {
      bool nowch = 1, block = 0;
      for(int k = -1; k <= 1; ++k)
        for(int l = -1; l <= 1; ++l)
          if(k + i >= 0 && k + i < h && l + j >= 0 &&
             l + j < w) {
            if(c[k + i][l + j] == '*') nowch = 0;
            if(c[k + i][l + j] == '#') block = 1;
          }
      ch[i][j] = nowch & block;
    }
  solve();
  if(ans == inf)
    cout << "INF" << endl;
  else
    cout << ans << endl;
  return 0;
}

void solve() {
  priority_queue<pair<int, pair<int, int>>,
                 vector<pair<int, pair<int, int>>>,
                 greater<pair<int, pair<int, int>>>>
      pq;
  pq.push({0, {s.fi, s.se}});
  while(!pq.empty()) {
    pair<int, pair<int, int>> now, nextp;
    now = pq.top();
    pq.pop();
    if(memo[now.se.fi][now.se.se] < now.fi) continue;
    for(int i = 0; i < 4; ++i) {
      nextp = now;
      nextp.se.fi += d[i];
      nextp.se.se += d[i ^ 1];
      nextp.fi += a;
      if(nextp.se.fi < 0 || nextp.se.fi >= h ||
         nextp.se.se < 0 || nextp.se.se >= w ||
         memo[nextp.se.fi][nextp.se.se] <= nextp.fi)
        continue;
      if(c[nextp.se.fi][nextp.se.se] == '#') {
        if(ch[now.se.fi][now.se.se] &&
           memo[nextp.se.fi][nextp.se.se] > nextp.fi + b)
          nextp.fi += b;
        else
          continue;
      }
      memo[nextp.se.fi][nextp.se.se] = nextp.fi;
      pq.push(nextp);
    }
    if(!ch[now.se.fi][now.se.se]) continue;
    for(int i = 0; i < 4; ++i) {
      nextp = now;
      nextp.se.fi += ds[i];
      nextp.se.se += ds[(i + 1) % 4];
      nextp.fi += 2 * a + b;
      if(nextp.se.fi < 0 || nextp.se.fi >= h ||
         nextp.se.se < 0 || nextp.se.se >= w ||
         c[nextp.se.fi][nextp.se.se] != '#' ||
         memo[nextp.se.fi][nextp.se.se] <= nextp.fi)
        continue;
      memo[nextp.se.fi][nextp.se.se] = nextp.fi;
      pq.push(nextp);
    }
  }
  ans = memo[g.fi][g.se];
}
