Problem: Problem

Kotatsu turtle is a turtle with a kotatsu shell.


As soon as Kotatsu was pokita (getting up), he was trapped in a stage divided into grid-like sections. There is only one exit on this stage. The parcel is either a road, a fence or a bomb, and the kotatsu can move up, down, left and right to enter the parcel of the road or bomb. It cannot be moved diagonally. In addition, the fence section cannot be passed. The road section extends infinitely outside the stage, but it cannot be passed because there is a crocodile, the natural enemy of the turtle.

Kotatsu wants to go home (sleep) quickly, so I decided to head to the exit of this stage.

The kotatsu turtle, which can freely manipulate the infrared rays of the kotatsu, has the ability to turn eight sections around it into a road at the same time. However, if the 8 sections and one of the sections where you are located are bomb sections, the kotatsu will burn up when you explode, and you will not even be able to use the famous SNS "Kametta", so you will activate the ability. I can't do that.

<image>

An example is illustrated. The section where the illustration is not placed and the section where the kotatsu is placed are the sections of the road. The eight compartments around the kotatsu are the orange compartments. In the figure on the left, the 8 compartments around the kotatsu and the compartment where you are are not included in the bomb compartment, so you can activate the ability. However, in the figure on the right, the ability cannot be activated because the bomb compartment is included in either the surrounding 8 compartments or the compartment where you are.

The cost to move is $ A $ for each parcel move, and the cost to activate the ability is $ B $ each time. Please note that it is not the cost per wall turned into a road. The starting point and the exit of the stage are roads. Output the minimum sum of the cost of moving from the starting point to the exit of the stage and the cost of activating the ability. However, if you cannot reach the exit of the stage, output "INF" instead.

Constraints

The input satisfies the following conditions.

* $ 1 \ le H, W, A, B \ le 1000 $
* $ 3 \ le H + W $
* $ c_ {i, j} \ in $ {'s','g','.','#','*'}
*'s' and'g' appear once each

Input

The input is given in the following format.


$ H $ $ W $ $ A $ $ B $
$ c_ {1,1} \ cdots c_ {1, W} $
$ \ vdots $
$ c_ {H, 1} \ cdots c_ {H, W} $


The input consists of $ H + 1 $ lines.
On the $ 1 $ line, there are an integer $ H $ that represents the vertical length, an integer $ W $ that represents the left and right length, an integer $ A $ that represents the cost to move, and an integer $ B $ that represents the cost to activate the ability. Each is given with a blank delimiter.
The $ H $ line from the $ 2 $ line is given the state $ c_ {i, j} $ in each section of the stage where the kotatsu is confined.
$ c_ {i, j} $ consists of one of's','g','.','#','*', Each, and the partition $ (i, j) $ is in the following state. Represents that.
's': Indicates that the section is the starting point.
'g': Indicates that the parcel is the exit of the stage.
'.': Indicates that the section is a road.
'#': Indicates that the section is a fence.
'*': Indicates that the parcel is a bomb.

Output

Output the minimum sum of the cost of moving from the starting point to the exit of the stage and the cost of activating the ability. However, if you cannot reach the exit of the stage, output "INF" instead.

Examples

Input

4 4 1 1
g#..
#...
.*..
...s


Output

7


Input

4 4 1 1
g#..
...
.*..
...s


Output

7


Input

4 4 1 1
g#..
*..
....
...s


Output

INF


Input

2 4 1 1
g
s###


Output

6


Input

3 3 1 10
g..
.
s..


Output

6


Input

3 3 10 1
g..
.
s..


Output

21

Solution (in CPP):

Solution:
// need
#include <iostream>
#include <algorithm>
// data structure
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
//#include <deque>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <array>
// stream
//#include <istream>
#include <sstream>
//#include <ostream>
#include <fstream>
// etc
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>

// input
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest&...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); }
#define VEC_ROW(type, n, ...)std::vector<type> __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int w_=0; w_<n; ++w_){MACRO_VEC_ROW_Scan(w_, __VA_ARGS__);}
template<typename T> void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Init(int n, First& first, Rest&...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); }
template<typename T> void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Scan(int p, First& first, Rest&...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); }
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& R:c)for(auto& w:R)std::cin>>w;
// output
#define OUT(dist) std::cout<<(dist);
#define FOUT(n, dist) std::cout<<std::fixed<<std::setprecision(n)<<(dist);
#define SOUT(n, c, dist) std::cout<<std::setw(n)<<std::setfill(c)<<(dist);
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define ENDL std::cout<<std::endl;
#define FLUSH std::cout<<std::flush;
#define SHOW(dist) {std::cerr << #dist << "\t:" << (dist) << "\n";}
#define SHOWVECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}}
#define SHOWQUEUE(a) {auto tmp(a);std::cerr << #a << "\t:";while(!tmp.empty()){std::cerr << tmp.front() << " ";tmp.pop();}std::cerr << "\n";}
// utility
#define ALL(a) (a).begin(),(a).end()
#define FOR(w, a, n) for(int w=(a);w<(n);++w)
#define RFOR(w, a, n) for(int w=(n)-1;w>=(a);--w)
#define REP(w, n) for(int w=0;w<int(n);++w)
#define RREP(w, n) for(int w=int(n)-1;w>=0;--w)
#define FORLL(w, a, n) for(ll w=ll(a);w<ll(n);++w)
#define RFORLL(w, a, n) for(ll w=ll(n)-1;w>=ll(a);--w)
#define REPLL(w, n) for(ll w=0;w<ll(n);++w)
#define RREPLL(w, n) for(ll w=ll(n)-1;w>=0;--w)
#define IN(a, x, b) (a<=x && x<b)
template<class T> inline T CHMAX(T& a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; }
#define EXCEPTION(msg) throw std::string("Exception : " msg " [ in ") + __func__ + " : " + std::to_string(__LINE__) + " lines ]"
#define TRY(cond, msg) try {if (cond) EXCEPTION(msg);}catch (std::string s) {std::cerr << s << std::endl;}
//void CHECKTIME(std::function<void()> f) { auto start = std::chrono::system_clock::now(); f(); auto end = std::chrono::system_clock::now(); auto res = std::chrono::duration_cast<std::chrono::nanoseconds>((end - start)).count(); std::cerr << "[Time:" << res << "ns  (" << res / (1.0e9) << "s)]\n"; }
// test
template<class T> using V = std::vector<T>;
template<class T> using VV = V<V<T>>;

template<typename S, typename T>
std::ostream& operator<<(std::ostream& os, std::pair<S, T> p) {
	os << "(" << p.first << ", " << p.second << ")"; return os;
}

#define random_shuffle "USE std::shuffle!";

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = std::pair<int, int>;
using PAIRLL = std::pair<ll, ll>;
constexpr int INFINT = 1 << 30;                          // 1.07x10^ 9
constexpr int INFINT_LIM = (1LL << 31) - 1;              // 2.15x10^ 9
constexpr ll INFLL = 1LL << 60;                          // 1.15x10^18
constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62);  // 9.22x10^18
constexpr double EPS = 1e-6;
constexpr int MOD = 1000000007;
constexpr double PI = 3.141592653589793238462643383279;
template<class T, size_t N> void FILL(T(&a)[N], const T& val) { for (auto& x : a) x = val; }
template<class ARY, size_t N, size_t M, class T> void FILL(ARY(&a)[N][M], const T& val) { for (auto& b : a) FILL(b, val); }
template<class T> void FILL(std::vector<T>& a, const T& val) { for (auto& x : a) x = val; }
template<class ARY, class T> void FILL(std::vector<std::vector<ARY>>& a, const T& val) { for (auto& b : a) FILL(b, val); }
// ------------>8------------------------------------->8------------

int dy8[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dx8[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

signed main() {
	INIT;

	VAR(int, h, w, a, b);
	MAT(char, c, h, w);
	int sy, sx, gy, gx;
	REP(i, h) REP(j, w) {
		if (c[i][j] == 's') {
			sy = i; sx = j;
		}
		if (c[i][j] == 'g') {
			gy = i; gx = j;
		}
	}

	auto F = [&](int y, int x) { return y * w + x; };
	auto G = [&](int d) { return std::make_tuple(d / w, d % w); };

	std::vector<int> dist(h * w, INFLL);
	using P = std::pair<int, int>;
	std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
	dist[F(sy, sx)] = 0;
	pq.push(P(0, F(sy, sx)));
	while (!pq.empty()) {
		P p = pq.top(); pq.pop();
		int v = p.second;
		if (dist[v] < p.first) continue;
		int y, x;
		std::tie(y, x) = G(v);
		bool hasBomb = [&] {
			if (c[y][x] == '*') return true;
			REP(d, 8) {
				int dy = y + dy8[d];
				int dx = x + dx8[d];
				if (!IN(0, dy, h) || !IN(0, dx, w)) continue;
				if (c[dy][dx] == '*') return true;
			}
			return false;
		}();
		REP(d, 8) {
			int dy = y + dy8[d];
			int dx = x + dx8[d];
			if (!IN(0, dy, h) || !IN(0, dx, w)) continue;
			int cost = 0;
			int move = std::abs(dy8[d]) + std::abs(dx8[d]);
			if (move == 1) {
				cost = a;
				if (c[dy][dx] == '#') {
					if (!hasBomb) cost += b;
					else cost += INFINT;
				}
			}
			else {
				cost = a + a;
				if ((c[dy][dx] == '#' || (c[y][dx] == '#' && c[dy][x] == '#'))) {
					if (!hasBomb) cost += b;
					else cost += INFINT;
				}
			}
			if (dist[F(dy, dx)] > dist[v] + cost) {
				dist[F(dy, dx)] = dist[v] + cost;
				pq.push(P(dist[F(dy, dx)], F(dy, dx)));
			}
		}
	}
	if (dist[F(gy, gx)] >= INFINT) {
		OUT("INF")BR;
		return 0;
	}
	OUT(dist[F(gy, gx)])BR;

	return 0;
}