#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;
}



Measured memory_bytes: 234288