#include <iostream> #include <vector> #include <queue> #include <tuple> #include <algorithm> using namespace std; using ll = long long; const ll INF = 1e18; int H, W; ll A, B, C; int N; vector<pair<int, int>> players; ll pickup[505][505]; ll dist[505][505][3]; int dr[] = {0, 0, 1, -1}; int dc[] = {1, -1, 0, 0}; bool inside(int r, int c) { return r >= 0 && r <= H && c >= 0 && c <= W; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> H >> W; cin >> A >> B >> C; cin >> N; players.resize(N); for (int i = 0; i <= H; i++) { for (int j = 0; j <= W; j++) { pickup[i][j] = INF; for (int k = 0; k < 3; k++) dist[i][j][k] = INF; } } priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq_pickup; for (int i = 0; i < N; i++) { cin >> players[i].first >> players[i].second; pickup[players[i].first][players[i].second] = 0; pq_pickup.push({0, {players[i].first, players[i].second}}); } // Dijkstra for pickup costs (Multi-source) while (!pq_pickup.empty()) { ll d = pq_pickup.top().first; int r = pq_pickup.top().second.first; int c = pq_pickup.top().second.second; pq_pickup.pop(); if (d > pickup[r][c]) continue; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (inside(nr, nc)) { if (pickup[nr][nc] > d + C) { pickup[nr][nc] = d + C; pq_pickup.push({pickup[nr][nc], {nr, nc}}); } } } } // Main Dijkstra // State: 0 = Held, 1 = Vertical, 2 = Horizontal priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq; int startR = players[0].first; int startC = players[0].second; int targetR = players[N - 1].first; int targetC = players[N - 1].second; dist[startR][startC][0] = 0; pq.push({0, startR, startC, 0}); while (!pq.empty()) { auto [d, r, c, state] = pq.top(); pq.pop(); if (d > dist[r][c][state]) continue; // State 0: Held if (state == 0) { // Kick Vertical if (d + B < dist[r][c][1]) { dist[r][c][1] = d + B; pq.push({dist[r][c][1], r, c, 1}); } // Kick Horizontal if (d + B < dist[r][c][2]) { dist[r][c][2] = d + B; pq.push({dist[r][c][2], r, c, 2}); } // Walk with ball for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (inside(nr, nc)) { if (d + C < dist[nr][nc][0]) { dist[nr][nc][0] = d + C; pq.push({dist[nr][nc][0], nr, nc, 0}); } } } } // State 1: Flying Vertical else if (state == 1) { // Land if (d + pickup[r][c] < dist[r][c][0]) { dist[r][c][0] = d + pickup[r][c]; pq.push({dist[r][c][0], r, c, 0}); } // Continue Flying Vertical for (int i = 2; i < 4; i++) { // South, North int nr = r + dr[i]; int nc = c + dc[i]; if (inside(nr, nc)) { if (d + A < dist[nr][nc][1]) { dist[nr][nc][1] = d + A; pq.push({dist[nr][nc][1], nr, nc, 1}); } } } } // State 2: Flying Horizontal else if (state == 2) { // Land if (d + pickup[r][c] < dist[r][c][0]) { dist[r][c][0] = d + pickup[r][c]; pq.push({dist[r][c][0], r, c, 0}); } // Continue Flying Horizontal for (int i = 0; i < 2; i++) { // East, West int nr = r + dr[i]; int nc = c + dc[i]; if (inside(nr, nc)) { if (d + A < dist[nr][nc][2]) { dist[nr][nc][2] = d + A; pq.push({dist[nr][nc][2], nr, nc, 2}); } } } } } cout << dist[targetR][targetC][0] << "\n"; return 0; }