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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 1005

struct Edge{

	Edge(int arg_to_row,int arg_to_col, ll arg_cost){
		to_row = arg_to_row;
		to_col = arg_to_col;
		cost = arg_cost;
	}

	int to_row,to_col;
	int cost;
};

struct Info{
	Info(int arg_row,int arg_col, ll arg_sum_cost){
		row = arg_row;
		col = arg_col;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{
		return sum_cost > arg.sum_cost; //総コストの昇順(PQ)
	}

	int row,col;
	ll sum_cost;
};

int H,W;
int start_row,start_col,goal_row,goal_col;
int diff_row[9] = {-1,-1,-1,0,0,0,1,1,1},diff_col[9] = {-1,0,1,-1,0,1,-1,0,1};
int A,B;
char table[NUM][NUM];
vector<Edge> G[NUM][NUM];
int min_dist[NUM][NUM];


bool rangeCheck(int row,int col){

	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1){

		return true;
	}else{
		return false;
	}
}

int main(){

	scanf("%d %d %d %d",&H,&W,&A,&B);

	for(int row = 0; row < H; row++){

		scanf("%s",table[row]);
		for(int col = 0; col < W; col++){
			if(table[row][col] == 's'){

				start_row = row;
				start_col = col;
				table[row][col] = '.';

			}else if(table[row][col] == 'g'){

				goal_row = row;
				goal_col = col;
				table[row][col] = '.';
			}
		}
	}

	//各セルから、他のセルへエッジを張る
	bool is_bomb;
	int adj_row,adj_col;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){

			is_bomb = false;

			//隣接9区間に爆弾があるか調べる
			for(int i = 0; i < 9; i++){
				adj_row = row+diff_row[i];
				adj_col = col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				if(table[adj_row][adj_col] == '*'){
					is_bomb = true;
					break;
				}
			}

			for(int i = 0; i < 9; i++){

				adj_row = row+diff_row[i];
				adj_col = col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				switch(table[adj_row][adj_col]){
				case '.':

					if((abs(row-adj_row)+abs(col-adj_col) == 1)){ //隣

						G[row][col].push_back(Edge(adj_row,adj_col,A));

					}else{ //壁があって行けない場合あり

						if(table[row][adj_col] != '#' || table[adj_row][col] != '#'){
							G[row][col].push_back(Edge(adj_row,adj_col,2*A));
						}else{
							if(!is_bomb){
								G[row][col].push_back(Edge(adj_row,adj_col,2*A+B));
							}
						}
					}

					break;
				case '*':
					if((abs(row-adj_row)+abs(col-adj_col) == 1)){ //隣

							G[row][col].push_back(Edge(adj_row,adj_col,A));

						}else{ //壁があって行けない場合あり

							if(table[row][adj_col] != '#' || table[adj_row][col] != '#'){
								G[row][col].push_back(Edge(adj_row,adj_col,2*A));
							}
						}
					break;
				case '#':
					if(!is_bomb){
						G[row][col].push_back(Edge(adj_row,adj_col,A*(abs(row-adj_row)+abs(col-adj_col))+B));
					}
					break;
				}
			}
		}
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			min_dist[row][col] = HUGE_NUM;
		}
	}

	priority_queue<Info> Q;
	min_dist[start_row][start_col] = 0;

	Q.push(Info(start_row,start_col,0));

	int next_row,next_col,next_cost;

	while(!Q.empty()){

		if(Q.top().row == goal_row && Q.top().col == goal_col){

			printf("%d\n",Q.top().sum_cost);
			return 0;

		}else if(Q.top().sum_cost > min_dist[Q.top().row][Q.top().col]){

			Q.pop();

		}else{

			for(int i = 0; i < G[Q.top().row][Q.top().col].size(); i++){

				next_row = G[Q.top().row][Q.top().col][i].to_row;
				next_col = G[Q.top().row][Q.top().col][i].to_col;
				next_cost = Q.top().sum_cost+G[Q.top().row][Q.top().col][i].cost;

				if(min_dist[next_row][next_col] > next_cost){
					min_dist[next_row][next_col] = next_cost;
					Q.push(Info(next_row,next_col,next_cost));
				}
			}

			Q.pop();
		}
	}

	printf("INF\n");

	return 0;
}