//#include #include #include using namespace std; //using namespace atcoder; using ll = long long; #define all(A) A.begin(),A.end() using vll = vector; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) using Graph = vector>; Graph G; vll E; vector seen; ll k = 0; void dfs(int v) { seen[v] = true; // v を訪問済にする // v から行ける各頂点 next_v について E[v] = k; for (auto next_v : G[v]) { if (seen[next_v]) continue; // next_v が探索済だったらスルー k++; dfs(next_v); // 再帰的に探索 } E[v] = k - E[v]; } int main() { ll H,W; cin>>H>>W; ll U,D,R,L,K,P; cin>>U>>D>>R>>L>>K>>P; priority_queue,vector>,greater>> Q; ll XS,YS,XT,YT; cin>>XS>>YS>>XT>>YT; XS--;XT--;YS--;YT--; vector C(H,vll(W)); rep(h,H){ string S; cin>>S; rep(w,W){ if(S[w]=='.')C[h][w]=0; else if(S[w]=='@')C[h][w]=1; else C[h][w]=2; } } vector> seen(H,vector (W,false)); vector dist(H,vll(W,1e18)); dist[XS][YS]=0; Q.push(make_tuple(0,XS,YS)); vll dx={1,-1,0,0}; vll dy={0,0,1,-1}; vll dp={D,U,R,L}; while(!Q.empty()){ auto p=Q.top(); Q.pop(); ll c=get<0>(p); ll y=get<2>(p); ll x=get<1>(p); if(seen[x][y])continue; seen[x][y]=true; rep(i,4){ ll nx=x+dx[i]; ll ny=y+dy[i]; if(nx<0||x+dx[i]>=H||y+dy[i]<0||y+dy[i]>=W)continue; if(C[nx][ny]==2)continue; ll HH=0; if(C[nx][ny]==1)HH+=P; if(dist[nx][ny]