#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; int main() { int h, w; cin>>h>>w; ll c[4]; int dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, 1, -1}; for(int i=0; i<4; i++) cin>>c[i]; ll k, p; cin>>k>>p; ll d[101][101]; int xs, ys, xt, yt; cin>>xs>>ys>>xt>>yt; xs--; ys--; xt--; yt--; string s[101]; for(int i=0; i>s[i]; const ll INF=1e18; for(int i=0; i; priority_queue, greater> que; que.push({0, {xs, ys}}); while(!que.empty()){ auto q=que.top(); que.pop(); int x=q.second.first, y=q.second.second; if(q.first>d[x][y]) continue; for(int i=0; i<4; i++){ int x1=x+dx[i], y1=y+dy[i]; if(x1<0 || x1>=h || y1<0 || y1>=w) continue; if(s[x1][y1]=='#') continue; ll cost=c[i]; if(s[x1][y1]=='@') cost+=p; if(d[x1][y1]>d[x][y]+cost){ d[x1][y1]=d[x][y]+cost; que.push({d[x1][y1], {x1, y1}}); } } } //cout<