#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int,int> const int INF = 4e18; /* current state of the ball /pass 0 = up -> up again , stay 1 = right ... 2 = down... 3 = left... /move with 4 = the ball is being carried -> move udlr , pass udlr 5 = stay(the ball has been passed and stopped) */ int32_t main() { cin.tie(0)->sync_with_stdio(0); int h,w,a,b,c,n; cin>> h>> w>> a>> b>> c>> n; vector<pi> pos(n); for (int i=0; i<n; i++) cin>> pos[i].first>> pos[i].second; // {x, y, state} vector<vector<vector<int>>> dp(h+2, vector<vector<int>>(w+2, vector<int>(6, INF))); int stx=pos[0].second, sty=pos[0].first; int edx=pos[n-1].second, edy=pos[n-1].first; dp[sty][stx][4] = 0; priority_queue<pair<pi, pi>, vector<pair<pi, pi>>, greater<pair<pi, pi>>> pq;// {cost, state, x, y} pq.push({{0, 4}, {sty, stx}}); int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1}; vector<vector<int>> mndist(h+2, vector<int>(w+2, 0)); vector<vector<bool>> vst(h+2, vector<bool>(w+2, false)); queue<pair<int,int>> q; for (int i=0; i<n; i++) q.push({pos[i].first, pos[i].second}), vst[pos[i].first][pos[i].second]=true; while (!q.empty()) { int y=q.front().first, x=q.front().second; q.pop(); for (int e=0; e<4; e++) { int nx = x+dx[e], ny = y+dy[e]; if (nx <= w && nx >= 0 && ny <= h && ny >= 0) { if (vst[ny][nx]) continue; vst[ny][nx] = true; mndist[ny][nx] = mndist[y][x]+1; q.push({ny,nx}); } } } while (!pq.empty()) { pair<pi,pi> cur = pq.top(); pq.pop(); int cost = cur.first.first; int state = cur.first.second; int y = cur.second.first; int x = cur.second.second; if (dp[y][x][state] < cost) continue; if (state < 4) { int nx = x+dx[state], ny = y+dy[state]; if (nx <= w && nx >= 0 && ny <= h && ny >= 0) { if (dp[ny][nx][state] > dp[y][x][state] + a) { dp[ny][nx][state] = dp[y][x][state] + a; pq.push({{dp[ny][nx][state], state}, {ny, nx}}); } } if (dp[y][x][5] > dp[y][x][state]) { dp[y][x][5] = dp[y][x][state]; pq.push({{dp[y][x][5], 5}, {y, x}}); } } else if (state == 4) { for (int e=0; e<4; e++) { int nx = x+dx[e], ny = y+dy[e]; if (nx <= w && nx >= 0 && ny <= h && ny >= 0) { if (dp[ny][nx][state] > dp[y][x][state] + c) { dp[ny][nx][state] = dp[y][x][state] + c; pq.push({{dp[ny][nx][state], state}, {ny, nx}}); } } } for (int e=0; e<4; e++) { int nx = x+dx[e], ny = y+dy[e]; if (nx <= w && nx >= 0 && ny <= h && ny >= 0) { if (dp[ny][nx][e] > dp[y][x][state] + a + b) { dp[ny][nx][e] = dp[y][x][state] + a + b; pq.push({{dp[ny][nx][e], e}, {ny, nx}}); } } } } else if (state == 5) { if (dp[y][x][4] > dp[y][x][5]+mndist[y][x]*c) { dp[y][x][4] = dp[y][x][5]+mndist[y][x]*c; pq.push({{dp[y][x][4], 4}, {y, x}}); } } } cout<< dp[edy][edx][4]; }