#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007LL;
const int INF = MOD;
int di[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dj[8] = {1, 1, 0, -1, -1, -1, 0, 1};

vector<int> dijk(int s, int v, vector<vector<pair<int, int> > > adjlist){
    
    priority_queue <pair<int, int> > wait;
    vector<int> result(v, INF);

    //スタート地点を追加
    result[s] = 0;
    wait.push(make_pair(0, s));

    //ダイクストラ本体
    while(!wait.empty()){    //waitが空になるまで

        int nowpoint = wait.top().second;
        int nowcost = -wait.top().first;
        wait.pop();

        if(result[nowpoint] < nowcost) continue;

        //今いる頂点と隣接しているすべての頂点をなめる
        for(int i = 0; i < adjlist[nowpoint].size(); i++){

            int nextpoint = adjlist[nowpoint][i].second;
            int nextcost = nowcost + adjlist[nowpoint][i].first;
            //現時点より安く到達できそうであれば、結果を更新して優先度付きキューに格納
            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push(make_pair(-nextcost, nextpoint));
            }
        }
    }
    
    return result;         //結果列を返す
}

signed main(){
    
    int h, w, a, b; cin >> h >> w >> a >> b;
    vector<vector<char> > G(h + 2, vector<char> (w + 2, 'x'));
    
    int si, sj, gi, gj;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> G[i][j];
            if(G[i][j] == 's'){
                si = i;
                sj = j;
                G[i][j] = '.';
            }

            if(G[i][j] == 'g'){
                gi = i;
                gj = j;
                G[i][j] = '.';
            }
        }
    }

    int GridtoGraph[1010][1010];
    int num = 0;
    for(int i = 0; i <= h + 1; i++){
        for(int j = 0; j <= w + 1; j++){
            GridtoGraph[i][j] = num;
            num++;
        }
    }

    //first := コスト　second := 行先   
    vector<vector<pair<int, int> > > adjlist(num); 
    int s = GridtoGraph[si][sj];   
    int g = GridtoGraph[gi][gj];
    
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            int cur = GridtoGraph[i][j];
            
            bool isExist = false;   //爆弾が周りにあるか
            if(G[i][j] == '*') isExist = true;
            for(int h = 0; h < 8; h++){
                int ni = i + di[h];
                int nj = j + dj[h];
                if(G[ni][nj] == '*') isExist = true;
            }

            for(int h = 0; h < 8; h++){
                int ni = i + di[h];
                int nj = j + dj[h];
                if(G[ni][nj] == 'x') continue;

                //この時点で '.' '*' '#' の三通り

                int nxt = GridtoGraph[ni][nj];
                if(h % 2 == 0){
                    //上下左右の移動
                    if(G[ni][nj] == '#'){
                        if(isExist) continue;
                        adjlist[cur].push_back({a + b, nxt});
                    }else{
                        adjlist[cur].push_back({a, nxt});                        
                    }

                }else{
                    //斜め移動
                    int subi1 = i + di[h - 1];
                    int subj1 = j + dj[h - 1];
                    int subi2 = i + di[(h + 1) % 8];
                    int subj2 = j + dj[(h + 1) % 8];                    
                    
                    if(G[ni][nj] == '#' || G[subi1][subj1] == '#' || G[subi2][subj2] == '#'){
                        if(isExist) continue;
                        adjlist[cur].push_back({2 * a + b, nxt});                        
                    }else{
                        adjlist[cur].push_back({2 * a, nxt});
                    }
                }
            }
        }
    }

    vector<int> result(num);
    result = dijk(s, num, adjlist);
    int ans = result[g];
    if(ans == INF) cout << "INF" << endl;
    else cout << ans << endl;
    return 0;
}


Measured memory_bytes: 218760