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:
//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b-1,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int long long
#define zero 0LL
#define pb PB
using namespace std;
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<ppr, Vppr ,greater<ppr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
int dx[] = { 0,1,0,-1,1,1,-1,-1,0 }, dy[] = { 1,0,-1,0,1,-1,1,-1,0 };
const int SIZE1 =3e5 + 1000;
const int SIZE2 = 2010;
const int SIZE3 = 22;
const int SIZE = SIZE1;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
ut N, M, K, X, L, Y,H,W,Q,D;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE], nums[SIZE], maps[SIZE2][SIZE2], answer = zero;
//LL A[SIZE], B[SIZE];
bool nable[SIZE2][SIZE2];
LL cost[SIZE2][SIZE2];
LL A, B;
LL sy, sx, gy, gx;
LL solve() {
	cin >> H >> W >> A >> B;
	string s;
	REP(i, SIZE2) REP(j, SIZE2) cost[i][j] = INF;
	REP(i, H) {
		cin >> s;
		REP(j, W) {
			LL h=i+1, w=j+1;
			maps[h][w]=s[j]=='.';
			//cout << maps[i+1][j+1] << endl;
			if (s[j] == '*') {
				maps[h][w] = 1;
				EFOR(k, -1, 1) EFOR(l, -1, 1)
					nable[h + k][w + l] = true;
			}
			if (s[j] == 'g') {
				maps[h][w] = true;
				gy = h;
				gx = w;
			}
			else if (s[j] == 's') {
				maps[h][w] = true;
				sy = h;
				sx = w;

			}
		}
	}
	PQ qu;
	cost[sy][sx] = 0;
	qu.emplace(cost[sy][sx], pr(sy, sx));
	
	while (!qu.empty()) {
		pr now = qu.top().second;
		LL co = qu.top().first;
		qu.pop();
		LL h = now.first;
		LL w = now.second;
		if (h <= 0 or  h> H or w <= 0 or w> W) continue;
		assert(co >= cost[h][w]);
		if (co != cost[h][w]) continue;
		REP(i, 8) {
			int ny = dy[i] + h, nx = dx[i] + w;
			if (i < 4 and maps[ny][nx]) {
				if(MN(cost[ny][nx],co+A))
					qu.emplace(cost[ny][nx],pr(ny,nx));

			}
			else if (!nable[h][w]) {
				if (i < 4) {
					if (MN(cost[ny][nx], co + B+A))
						qu.emplace(cost[ny][nx],pr(ny,nx));
				}
				else {
					if (MN(cost[ny][nx], co + B + A+A))
						qu.emplace(cost[ny][nx],pr(ny,nx));
				}
			}
		}
	
	}
	if (cost[gy][gx] >= INF/2) {
		cout << "INF" << endl;
		return 0;
	}
	cout << cost[gy][gx] << endl;

	return 0;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	solve();
	//	cin >> N;
	return 0;
}