不知道是不是最短路打炸了。。。（不要问我为什么稠密图打spfa，问就是懒）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
#define debug printf("zjy\n")
ll read(){
	ll a=0,b=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')b=-1;c=getchar();}
	while(isdigit(c)){a=a*10+c-'0';c=getchar();}
	return a*b;
}
const ll N=4e5+50,M=2e7+50,inf=1e14+50;
ll n,k,wa,wb,wc,s,t,cnt,tot=1,h[N],ver[M],nx[M],w[M],
d[N],vis[N],ans;
ll dx[2]={0,1},dy[2]={1,0};
void add(ll u,ll v,ll val){
	ver[++tot]=v;w[tot]=val;nx[tot]=h[u];h[u]=tot;
}
queue<ll> q;
void spfa(){
	for(ll i=s;i<=t;i++)d[i]=inf;
	q.push(s);d[s]=0;
	vis[s]=1;
	while(!q.empty()){
		ll x=q.front();q.pop();
		vis[x]=0;
		for(ll i=h[x],v;i;i=nx[i]){
			v=ver[i];
			if(d[v]>d[x]+w[i]){
				d[v]=d[x]+w[i];
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
void connect(ll x,ll y){
	for(ll i=0,tx,ty;i<2;i++){
		tx=x+dx[i];ty=y+dy[i];
		if(tx>n||ty>n)continue;
		for(ll j=1,u,v;j<=k;j++){
			u=(j-1)*n*n+(x-1)*n+y;
			v=j*n*n+(tx-1)*n+ty;
			add(u,v,0);
			add(v-n*n,u+n*n,wb);
		}
	}
}
int main(){
	n=read();k=read();
	wa=read();wb=read();wc=read();
	s=1;t=n*n*(k+1);
	for(ll i=1;i<=n;i++){
		for(ll j=1,oil,now;j<=n;j++){
			connect(i,j);
			oil=read();
			now=(i-1)*n+j;
			for(ll o=1,u=now;o<=k;o++){
				u+=n*n;
				if(oil)add(u,now,wa);
				else add(u,now,wa+wc);
			}
		}
	}
	for(ll i=1,u,v;i<=k;i++){
		u=n*n*i;v=n*n*(i+1);
		add(u,v,0);
	}
	spfa();
	printf("%lld\n",d[t]);
	return 0;
}