#include<bits/stdc++.h>
#define rt register int
#define ll long long
using namespace std;
ll n,m,A,B,C,a[30005],f[30005][35],t,fi[30005],ans=1e9;
bool pd[30005][25];
struct p{
	ll ne,to;
}l[100005];
void add(ll x,ll y){
	l[++t].ne=fi[x];
	l[t].to=y;
	fi[x]=t;
}
struct data{
	ll w,s;
};
void spfa(){
	queue<data>q;q.push(data{1,m}),pd[1][m]=true;
	while(!q.empty()){
		data u=q.front();pd[u.w][u.s]=false;q.pop();
		for(rt i=fi[u.w];i;i=l[i].ne){int v=l[i].to;
			if(a[v]){if(f[u.w][u.s]+A+(v<u.w?B:0)+(u.s?0:C)<f[v][m]){
				f[v][m]=f[u.w][u.s]+A+(v<u.w?B:0)+(u.s?0:C);
				if(!pd[v][m])q.push(data{v,m}),pd[v][m]=true;
			}
			}
			else if(!u.s){if(f[u.w][u.s]+C+(v<u.w?B:0)+A<f[v][m-1]){
				f[v][m-1]=f[u.w][u.s]+C+(v<u.w?B:0)+A;
				if(!pd[v][m-1])q.push(data{v,m-1}),pd[v][m-1]=true;
			}
			}
			else if(f[u.w][u.s]+(v<u.w?B:0)<f[v][u.s-1]){
				f[v][u.s-1]=f[u.w][u.s]+(v<u.w?B:0);
				if(!pd[v][u.s-1])q.push(data{v,u.s-1}),pd[v][u.s-1]=true;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>A>>B>>C;
	for(rt i=0;i<n;i++)for(rt j=1;j<=n;j++){
		cin>>a[i*n+j];
		if(i>1)add(i*n+j,i*n+j-n);
		if(j>1)add(i*n+j,i*n+j-1);
		if(i%n!=0||i==0)add(i*n+j,i*n+j+1);
		if(i!=n)add(i*n+j,i*n+j+n);
	}
	for(rt i=1;i<=n*n;i++)for(rt j=0;j<=m;j++)f[i][j]=1e9;f[1][m]=0;
	spfa();
	for(rt i=0;i<=m;i++)ans=min(ans,f[n*n][i]);
	cout<<ans;
    return 0;
}