#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;

signed main(){
    i64 h, w, a, b;
    cin >> h >> w >> a >> b;
    vector<i64> dx = {1, 0, -1, 0, 1, 1, -1, -1, 0};
    vector<i64> dy = {0, 1, 0, -1, 1, -1, 1, -1, 0};
    vector<string> s(h);
    for(auto& x : s)
        cin >> x;
    i64 st_x, st_y, en_x, en_y;
    for(i64 i = 0; i < h; ++i)
        for(i64 j = 0; j < w; ++j){
            if(s[i][j] == 's'){
                st_x = i;
                st_y = j;
            }
            if(s[i][j] == 'g'){
                en_x = i;
                en_y = j;
            }
        }
    priority_queue<tuple<i64,i64,i64>, vector<tuple<i64,i64,i64>>, greater<tuple<i64,i64,i64>>> que;
    vector<vector<i64>> range(h, vector<i64>(w, INF));
    range[st_x][st_y] = 0;
    que.emplace(0, st_x, st_y);
    while(!que.empty()){
       i64 dist, x, y;
       tie(dist, x, y) = que.top();
       que.pop();
       bool fl = true;
       for(i64 i = 0; i < 9; ++i){
           i64 xx = x + dx[i];
           i64 yy = y + dy[i];
           if(xx >= 0 && xx < h && yy >= 0 && yy < w && s[xx][yy] == '*')
               fl = false;
       }
       for(i64 i = 0; i < (fl ? 8 : 4); ++i){
           i64 xx = x + dx[i];
           i64 yy = y + dy[i];
           if(!(xx >= 0 && xx < h && yy >= 0 && yy < w))
               continue;
           // 移動にかかるcost
           i64 cost = range[x][y] + a * (i / 4 + 1);
           // ほげ
           if(!fl && s[xx][yy] == '#')
               continue;
           if(s[xx][yy] == '#' || i >= 4)
               cost += b;
           if(range[xx][yy] > cost){
               range[xx][yy] = cost;
               que.emplace(cost, xx, yy);
           }
       }
    }
    if(range[en_x][en_y] >= 1e15)
        cout << "INF" << endl;
    else
        cout << range[en_x][en_y] << endl;
}

