#include <bits/stdc++.h>
using namespace std;
//#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "")
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

template<typename T>
class Dijk {
private:
    template <typename U> using Edge = pair<ll, U>;
    template <typename U> using Edges = vector<Edge<U>>;
    template <typename U> using PQ = priority_queue<pair<ll, U>, vector<pair<ll, U>>, function<bool(pair<ll, U>, pair<ll, U>)>>;
    
    const vector<Edges<T>> &edges;
    T inf;
    T identity_ele;
        
public:
    Dijk(const vector<Edges<T>> &edges, T inf, T identity_ele)
        : edges(edges),
          inf(inf),
          identity_ele(identity_ele) {}

    vector<T> dijk(ll start, ll goal = -1) {
        vector<T> d(edges.size(), inf);
        d[start] = identity_ele;
        PQ<T> q([&](const Edge<T> &a, const Edge<T> &b) {return a.second > b.second;});
        q.push(make_pair(start, 0));
        while(q.size()) {
            ll now;
            T dis;
            tie(now, dis) = q.top();
            q.pop();
            if(d[now] < dis) {
                continue;
            }
            if(now == goal) break;
            for(const auto &e : edges[now]) {
                ll nxt;
                T cost;
                tie(nxt, cost) = e;
                if(d[nxt] == inf || dis + cost < d[nxt]) {
                    d[nxt] = dis + cost;
                    q.push(make_pair(nxt, dis + cost));
                }
            }
        }
        return d;
    }
};

const ll INF = 1e9;
V<string> S;
ll dd[] = {1, 0, -1};
ll dh[] = {1, 0, -1, 0};
ll dw[] = {0, 1, 0, -1};
ll H, W, A, B;

bool check_range(ll i, ll j) {
    return 0 <= i && i < H && 0 <= j && j < W;
}

bool check_bom(ll h, ll w) {
    for(ll i = 0; i < 3; i++) for(ll j = 0; j < 3; j++) {
        ll nh = h + dd[i], nw = w + dd[j];
        if(!check_range(nh, nw)) continue;
        if(S[nh][nw] == '*') return true;
    }
    return false;
}

ll ID(ll i, ll j) { return W * i + j; }
ll ID(PLL p) { return ID(p.first, p.second); }

int main() {
    cin >> H >> W >> A >> B;
    S = V<string>(H);
    for(string &s : S) cin >> s;
    PLL start, goal;
    for(ll i = 0; i < H; i++) for(ll j = 0; j < W; j++) {
        if(S[i][j] == 's') start = PLL(i, j);
        if(S[i][j] == 'g') goal = PLL(i, j);
    }
    VV<PLL> edges(H * W);
    for(ll i = 0; i < H; i++) for(ll j = 0; j < W; j++) {
        bool bom = check_bom(i, j);
        for(ll d = 0; d < 4; d++) {
            ll ni = i + dh[d], nj = j + dw[d];
            if(!check_range(ni, nj)) continue;
            if(S[ni][nj] == '.' || S[ni][nj] == 'g' || S[ni][nj] == '*') edges[ID(i, j)].emplace_back(ID(ni, nj), A);
            if(!bom) {
                edges[ID(i, j)].emplace_back(ID(ni, nj), A + B);
                for(ll nd = 0; nd < 4; nd++) {
                    ll nni = ni + dh[nd], nnj = nj + dw[nd];
                    if(!(abs(i - nni) == 1 && abs(j - nnj) == 1)) continue;
                    if(!check_range(nni, nnj)) continue;
                    edges[ID(i, j)].emplace_back(ID(nni, nnj), B + 2 * A);
                }
            }
        }
    }
    for(auto &e : edges) {
        sort(ALL(e));
        V<PLL> tmp;
        ll pre = -1;
        for(const auto &ee : e) {
            if(pre == ee.first) continue;
            pre = ee.first;
            tmp.push_back(ee);
        }
        e = tmp;
    }
    S.clear();
    auto dist = move(Dijk<ll>(edges, INF, 0).dijk(ID(start), ID(goal)));
    DEBUG(edges);
    DEBUG(dist);
    DEBUG(ID(start));
    if(dist[ID(goal)] == INF) cout << "INF";
    else cout << dist[ID(goal)];
    cout << endl;
    return 0;
}



Measured memory_bytes: 171468