rt，调不出来

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >heap;
int fi[1000001],nx[6000001],to[6000001],tot,vis[6000001];
long long co[6000001],dis[6000001];
long long n,k,a,b,c;
void link(int a,int b,int c){
	nx[++tot]=fi[a];
	fi[a]=tot;
	to[tot]=b;
	co[tot]=c;
}
int main(){
	int x;
	cin>>n>>k>>a>>b>>c;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>x;
			if(x==0){
				if(i>=1){
					for(int s=k;s>=1;s--){
						link(s*10000+(i-1)*100+j,(s-1)*10000+i*100+j,0);
						link(s*10000+(i-1)*100+j,k*10000+i*100+j,a+c);
					}	
				}
				if(j>=1){
					for(int s=k;s>=1;s--){
						link(s*10000+i*100+j-1,(s-1)*10000+i*100+j,0);
						link(s*10000+i*100+j-1,k*10000+i*100+j,a+c);
					}
				}
				if(i<n-1){
					for(int s=k;s>=1;s--){
						link(s*10000+(i+1)*100+j,(s-1)*10000+i*100+j,b);
						link(s*10000+(i+1)*100+j,k*10000+i*100+j,a+c+b);
					}
				}
				if(j<n-1){
					for(int s=k;s>=1;s--){
						link(s*10000+i*100+j+1,(s-1)*10000+i*100+j,b);
						link(s*10000+i*100+j+1,k*10000+i*100+j,a+c+b);
					}
				}
			}
			else{
				if(i>=1){
					for(int s=k;s>=1;s--){
						link(s*10000+(i-1)*100+j,k*10000+i*100+j,a);
					}	
				}
				if(j>=1){
					for(int s=k;s>=1;s--){
						link(s*10000+i*100+j-1,k*10000+i*100+j,a);
					}
				}
				if(i<n-1){
					for(int s=k;s>=1;s--){
						link(s*10000+(i+1)*100+j,k*10000+i*100+j,a+b);
					}
				}
				if(j<n-1){
					for(int s=k;s>=1;s--){
						link(s*10000+i*100+j+1,k*10000+i*100+j,a+b);
					}
				}
			}
		}
	}
	memset(dis,-1,sizeof(dis));
	heap.push(make_pair(0,k*10000));
	while(!heap.empty()){
		int co_st=heap.top().first;
		int now=heap.top().second;
		heap.pop(); 
		if(vis[now]){
			continue;
		}
		vis[now]=1;
		dis[now]=co_st;
		for(int i=fi[now];i;i=nx[i]){
			int v=to[i];
			if(!vis[i]&&(dis[v]==-1||dis[v]>dis[now]+co[i])){
				dis[v]=dis[now]+co[i];
				heap.push(make_pair(dis[v],v));	
			}
		}
	}
	long long mnn=0x7ffffff;
	for(int i=0;i<=k;i++)	{
		if(dis[i*10000+(n-1)*100+n-1]!=-1){ 
			mnn=min(mnn,dis[i*10000+(n-1)*100+n-1]);
		} 
	}
	cout<<mnn<<endl;
}