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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define SZ(i) int(i.size())
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"#%d: %s = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
template<typename It> ostream& _printRng(ostream &os,It bg,It ed)
{
    os<<"{";
    for(It it=bg;it!=ed;it++) {
        os<<(it==bg?"":",")<<*it;
    }
    os<<"}";
    return os;
}
template<typename T> ostream &operator << (ostream &os,vector<T> &v){return _printRng(os,v.begin(), v.end());}
template<typename T> void pary(T bg, T ed){_printRng(cerr,bg,ed);cerr<<endl;}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#define pary(...)
#endif

const int MAXN = 41;
const int MAXD = 4*MAXN*MAXN + 11;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int n, m, a, b, c, s, t;
bool blk;

int id (int x, int y) { // bh, !bv, !wh wv
    return (x * m + y) * 4;
}

struct Edge {
    int t, cap, flow, nxt;
} edge[50*MAXD];
int cnt, cur[MAXD], head[MAXD], lev[MAXD];

void add_edge (int F, int T, int C) {
//    debug(F, T, C);
    edge[cnt] = {T, C, 0, head[F]};
    head[F] = cnt++;
    edge[cnt] = {F, 0, 0, head[T]};
    head[T] = cnt++;
}

int dfs (int nd ,int lim) {
    if (nd == t || lim == 0) {
        return lim;
    }
    for (int &it=cur[nd]; it!=-1; it=edge[it].nxt) {
        int u = edge[it].t;
        int rem = edge[it].cap - edge[it].flow;

        if (lev[u] == lev[nd] + 1 && rem > 0) {
            int df;
            if (df = dfs(u, min(lim, rem))) {
                edge[it].flow += df;
                edge[it^1].flow -= df;
                return df;
            }
        }
    }
    return 0;
}


bool bfs () {
    vector<int> que;
    memset(lev, -1, sizeof(lev));
    lev[s] = 0;
    que.eb(s);

    while (que.size()) {
        int nd = que.back();
        que.pop_back();

        for (int it=head[nd]; it!=-1; it=edge[it].nxt) {
            int u = edge[it].t;
            if (lev[u] == -1 && edge[it].cap > edge[it].flow) {
                lev[u] = lev[nd] + 1;
                que.eb(u);
            }
        }
    }

    return lev[t] != -1;
}

int Dinic () {
    int flow = 0;
    while (bfs()) {
        REP (i, t+1) {
            cur[i] = head[i];
        }
        int df = 0;
        while (df = dfs(s, INF)) {
            flow += df;
        }
    }
    return flow;
}
/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n >> m >> a >> b >> c;
    memset(head, -1, sizeof(head));

    s = id(n-1,m-1) + 4, t = id(n-1,m-1) + 5;
    REP (x, n) {
        REP (y, m) {
            char ch;
            #ifdef tmd
            blk = rand() % 2;
            #else
            cin >> ch;
            blk = ch == '#';
            #endif // tmd

            int bh = id(x, y);
            int nbv = id(x, y) + 1;
            int nwh = id(x, y) + 2;
            int wv = id(x, y) + 3;

            if (x > 0) {
                add_edge(bh, id(x-1,y), b);
                add_edge(id(x-1,y)+2, nwh, b);
            } else {
                add_edge(bh, t, b);
                add_edge(s, nwh, b);
            }

            if (y > 0) {
                add_edge(wv, id(x,y-1)+3, b);
                add_edge(id(x,y-1)+1, nbv, b);
            }  else {
                add_edge(wv, t, b);
                add_edge(s, nbv, b);
            }

            add_edge(bh, t, a);
            add_edge(wv, t, a);
            add_edge(s, nbv, a);
            add_edge(s, nwh, a);

            if (blk) {
                add_edge(wv, t, INF);
                add_edge(s, nwh, INF);
                add_edge(nbv, bh, c);
            } else {
                add_edge(bh, wv, c);
                add_edge(nwh, nbv, c);
                add_edge(bh, nbv, INF);
            }
        }
    }
    debug("built");

    cout << Dinic() << endl;
}
/*
1 1 1 1 1
#
*/