#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

namespace sub {
    template<typename T>
    constexpr typename std::enable_if<std::is_integral<T>::value, T>::type
    inf_sub() {
        return std::numeric_limits<T>::max() / 2 - 1000;
    }

    template<typename T>
    constexpr typename std::enable_if<std::is_floating_point<T>::value, T>::type
    inf_sub() {
        return std::min(std::numeric_limits<T>::max() / 2 - 1000, T(1e50));
    }
}  // namespace sub

template<typename T>
constexpr T inf() {
    static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
    return sub::inf_sub<T>();
}

template<typename T>
constexpr T zero() {
    static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
    return T(0);
}


char c[1010][1010];
ll bad[1010][1010];
ll dst[1010][1010];
int H, W;
int A, B;

struct NODE {
    int r, c;
    ll cst;

    bool operator<(const NODE &rhs) const {
        return cst > rhs.cst;
    }
};

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};


ll dijkstra(int sy, int sx, int gy, int gx) {
    priority_queue<NODE> Q;
    for(int i = 0 ; i < 1010 ; i++)
        for(int j = 0 ; j < 1010 ; j++)
            dst[i][j] = inf<ll>();

    auto add = [&](int sy, int sx, ll cst) {
        if (cst >= dst[sy][sx]) return;
        Q.push({sy, sx, cst});
        dst[sy][sx] = cst;
    };

    add(sy, sx, 0);


    while (Q.size()) {
        auto q = Q.top();
        Q.pop();
        if (q.r == gy && q.c == gx) {
            return q.cst;
        }

        for (int d = 0; d < 4; d++) {
            int y = q.r + dy[d];
            int x = q.c + dx[d];
            if (x < 0 || y < 0 || x >= W || y >= H || c[y][x] == '#') continue;
            add(y, x, q.cst + A);
        }
        if( bad[q.r][q.c] ) continue;
        for (int x = -1; x <= 1; x++) {
            for (int y = -1; y <= 1; y++) {
                int I = q.r + y;
                int J = q.c + x;
                if (I < 0 || J < 0 || I >= H || J >= W)
                    continue;
                add(I, J, q.cst + B + A * (abs(x) + abs(y)));
            }
        }
    }
    return inf<ll>();
}

int main() {
    cin >> H >> W >> A >> B;

    int sx, sy, gx, gy;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> c[i][j];
            if (c[i][j] == '*') {
                for (int x = -1; x <= 1; x++) {
                    for (int y = -1; y <= 1; y++) {
                        int I = i + y;
                        int J = j + x;
                        if (I < 0 || J < 0 || I >= H || J >= W)
                            continue;
                        bad[I][J] = true;
                    }
                }
            } else if (c[i][j] == 's') {
                sx = j;
                sy = i;
            } else if (c[i][j] == 'g') {
                gx = j;
                gy = i;
            }
        }
    }
    auto ans = dijkstra(sy, sx, gy, gx);
    if (ans >= inf<ll>()) {
        cout << "INF" << endl;
    } else {
        cout << ans << endl;
    }


}


Measured memory_bytes: 19860