#include using namespace std; #include using namespace atcoder; using ll=long long; using Graph=vector>; #define MAX 2000000 #define MOD 1000000007 #define INF 1000000000000000000 int di[4]={1,0,-1,0}; int dj[4]={0,1,0,-1}; int main(){ int H,W; cin>>H>>W; ll U,D,R,L,K,P; cin>>U>>D>>R>>L>>K>>P; int xs,ys,xt,yt; cin>>xs>>ys>>xt>>yt; xs--;ys--;xt--;yt--; vector> C(H,vector(W)); for(int i=0;i>C[i][j]; } } vector> dist(H,vector(W,INF)); ll cost[4]={D,R,U,L}; priority_queue,vector>,greater>> pq; dist[xs][ys]=0; pq.push(make_pair(dist[xs][ys],xs*W+ys)); while(!pq.empty()){ int i=pq.top().second/W; int j=pq.top().second%W; ll d=pq.top().first; pq.pop(); if(dist[i][j]=H||nj>=W){ continue; } if(C[ni][nj]=='#'){ continue; } if(C[ni][nj]=='.'){ if(dist[ni][nj]>dist[i][j]+cost[k]){ dist[ni][nj]=dist[i][j]+cost[k]; pq.push(make_pair(dist[ni][nj],ni*W+nj)); } }else{ if(dist[ni][nj]>dist[i][j]+cost[k]+P){ dist[ni][nj]=dist[i][j]+cost[k]+P; pq.push(make_pair(dist[ni][nj],ni*W+nj)); } } } } //cout<