Problem: Draw in Straight Lines

You plan to draw a black-and-white painting on a rectangular canvas. The painting will be a grid array of pixels, either black or white. You can paint black or white lines or dots on the initially white canvas.

You can apply a sequence of the following two operations in any order.

* Painting pixels on a horizontal or vertical line segment, single pixel wide and two or more pixel long, either black or white. This operation has a cost proportional to the length (the number of pixels) of the line segment multiplied by a specified coefficient in addition to a specified constant cost.
* Painting a single pixel, either black or white. This operation has a specified constant cost.



You can overpaint already painted pixels as long as the following conditions are satisfied.

* The pixel has been painted at most once before. Overpainting a pixel too many times results in too thick layers of inks, making the picture look ugly. Note that painting a pixel with the same color is also counted as overpainting. For instance, if you have painted a pixel with black twice, you can paint it neither black nor white anymore.
* The pixel once painted white should not be overpainted with the black ink. As the white ink takes very long to dry, overpainting the same pixel black would make the pixel gray, rather than black. The reverse, that is, painting white over a pixel already painted black, has no problem.



Your task is to compute the minimum total cost to draw the specified image.

Input

The input consists of a single test case. The first line contains five integers $n$, $m$, $a$, $b$, and $c$, where $n$ ($1 \leq n \leq 40$) and $m$ ($1 \leq m \leq 40$) are the height and the width of the canvas in the number of pixels, and $a$ ($0 \leq a \leq 40$), $b$ ($0 \leq b \leq 40$), and $c$ ($0 \leq c \leq 40$) are constants defining painting costs as follows. Painting a line segment of length $l$ costs $al + b$ and painting a single pixel costs $c$. These three constants satisfy $c \leq a + b$.

The next $n$ lines show the black-and-white image you want to draw. Each of the lines contains a string of length $m$. The $j$-th character of the $i$-th string is ‘#’ if the color of the pixel in the $i$-th row and the $j$-th column is to be black, and it is ‘.’ if the color is to be white.

Output

Output the minimum cost.

Sample Input 1


3 3 1 2 3
.#.

.#.


Sample Output 1


10


Sample Input 2


2 7 0 1 1
.###
.###


Sample Output 2


3


Sample Input 3


5 5 1 4 4
..#..
..#..
.##
..#..
..#..


Sample Output 3


24


Sample Input 4


7 24 1 10 10
...###..#####....###.
.#...#...#.#....#..#...#
.#..#......#....#.#.....
.#..#......#####..#.....
.#..#......#......#.....
.#...#...#.#.......#...#
...###..#........###.


Sample Output 4


256






Example

Input

3 3 1 2 3
.#.
###
.#.


Output

10

Solution (in CPP):

Solution:
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<assert.h>
#include<set>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<iostream>
#include<bitset>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
#define per(i,j,k) for(int i=(int)(j);i>=(int)(k);i--)
using namespace std;
typedef long long LL;
typedef double db;
const int inf=1e9;
namespace h{
	const int N=43*43*4;
	int head[N],np[N*20],p[N*20],flow[N*20],tot;
	int S,T;
	void init(int n){
		S=n+1;
		T=n+2;
		rep(i,1,T)head[i]=0;
		rep(i,1,tot){
			p[i]=np[i]=flow[i]=0;
		}
		tot=1;
	}
	void add(int a ,int b,int c){
		++tot;p[tot]=b;np[tot]=head[a];head[a]=tot;flow[tot]=c;
		++tot;p[tot]=a;np[tot]=head[b];head[b]=tot;flow[tot]=0;
	}
	void ax(int x,int a){
		//贡献 ax
		add(S,x,a);
	}
	void a1_x(int x,int a){
		//贡献 a(1-x)
		add(x,T,a);
	}
	void cx1_y(int x,int y,int c){
		//贡献 cx(1-y)
		add(y,x,c);
	}
	int q[N],dis[N];
	int bfs(){
		rep(i,1,T)dis[i]=-1;
		q[q[0]=1]=S;
		dis[S]=0;
		rep(i,1,q[0]){
			int x=q[i];
			for(int u=head[x];u;u=np[u])if(dis[p[u]]==-1)if(flow[u]){
				dis[p[u]]=dis[x]+1;
				q[++q[0]]=p[u];
			}
		}
		return dis[T];
	}
	int dinic(int x,int ff){
		int res=0;
		if(x==T)return ff;
		for(int u=head[x];u;u=np[u])if(dis[p[u]]==dis[x]+1)if(flow[u]){
			int ret=dinic(p[u],min(ff,flow[u]));
			flow[u]-=ret;
			flow[u^1]+=ret;
			ff-=ret;
			res+=ret;
			if(!ff)break;
		}
		if(!res)dis[x]=-1;
		return res;
	}
	int calc(){
		int ans=0;
		while(bfs()!=-1)ans+=dinic(S,1e9);
		return ans;
	}
};
const int N=45;
int n,m,ca,cb,cc;
char s[N][N];
int bh[N][N],_wh[N][N],_bv[N][N],wv[N][N];
int t;
void Main(){
	scanf("%d%d%d%d%d",&n,&m,&ca,&cb,&cc);
	rep(i,1,n)scanf("%s",s[i]+1);
	t=0;
	rep(i,1,n)rep(j,1,m){
		bh[i][j]=++t;
		wv[i][j]=++t;
		_wh[i][j]=++t;
		_bv[i][j]=++t;
	}
	h::init(t);
	//cost of paint h or v
	rep(i,1,n)rep(j,1,m){
		h::ax(bh[i][j],ca);
		h::ax(wv[i][j],ca);
		h::a1_x(_wh[i][j],ca);
		h::a1_x(_bv[i][j],ca);

		if(j+1<=m){
			h::cx1_y(bh[i][j],bh[i][j+1],cb);
			h::cx1_y(_wh[i][j+1],_wh[i][j],cb);
		}
		else{
			h::ax(bh[i][j],cb);
			h::a1_x(_wh[i][j],cb);
		}

		if(i+1<=n){
			h::cx1_y(wv[i][j],wv[i+1][j],cb);
			h::cx1_y(_bv[i+1][j],_bv[i][j],cb);
		}
		else{
			h::ax(wv[i][j],cb);
			h::a1_x(_bv[i][j],cb);
		}
	}
	//cost of paint single dot
	rep(i,1,n)rep(j,1,m){
		if(s[i][j]=='#'){
			//black
			
			//前面不能往这里涂白，只要涂白就是inf
			h::ax(wv[i][j],inf);
			h::a1_x(_wh[i][j],inf);
			//如果没被涂过，就要 c 的代价
			h::cx1_y(_bv[i][j],bh[i][j],cc);
		}
		else{
			//white

			//涂了黑且没涂白就要 c 的代价，因为同一个格子不可能被hh,vv，所以只有两种情况
			h::cx1_y(bh[i][j],wv[i][j],cc);
			h::cx1_y(_wh[i][j],_bv[i][j],cc);
			//涂了两次黑，就是inf
			h::cx1_y(bh[i][j],_bv[i][j],inf);
		}
	}
	printf("%d\n",h::calc());
}
int main(){
	int t=1;
	while(t--)Main();
	return 0;
}