/* Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528) */ #include <bits/stdc++.h> using namespace std; #define int long long #define ull unsigned long long #define ld long double #define pii pair<int, int> #define fi first #define se second #define __builtin_popcount __builtin_popcountll #define all(x) (x).begin(), (x).end() #define BIT(x, i) (((x) >> (i)) & 1) #define MASK(x) ((1ll << (x))) #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; struct DijkstraState { int cost, x, y, d; bool operator > (const DijkstraState &other) const { return cost > other.cost; } }; const int MAXN = 1e5 + 5; const int MAXH = 505; const int INF = 1e18 + 5; int h, w, a, b, c, n; pii balls[MAXN]; void init() { cin >> h >> w >> a >> b >> c >> n; for (int i = 1; i <= n; ++i) { int x, y; cin >> x >> y; balls[i] = {x, y}; } } int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, 1, -1}; int cost[MAXH][MAXH]; int dist[MAXH][MAXH][5]; bool inside(int x, int y) { bool cond1 = (0 <= x && x <= h); bool cond2 = (0 <= y && y <= w); return (cond1 && cond2); } void prepare_cost() { for (int i = 0; i <= h; ++i) for (int j = 0; j <= w; ++j) cost[i][j] = INF; queue<pii> bfsQueue; for (int i = 1; i <= n; ++i) { int x = balls[i].fi, y = balls[i].se; cost[x][y] = 0; bfsQueue.push({x, y}); } while (!bfsQueue.empty()) { pii cur = bfsQueue.front(); int x = cur.fi, y = cur.se; bfsQueue.pop(); for (int nxt_dir = 0; nxt_dir < 4; ++nxt_dir) { int nx = x + dx[nxt_dir]; int ny = y + dy[nxt_dir]; if (!inside(nx, ny)) continue; int newcost = cost[x][y] + 1; if (cost[nx][ny] > newcost) { cost[nx][ny] = newcost; bfsQueue.push({nx, ny}); } } } } void dijkstra() { for (int i = 0; i <= h; ++i) for (int j = 0; j <= w; ++j) for (int d = 0; d <= 4; ++d) dist[i][j][d] = INF; priority_queue<DijkstraState, vector<DijkstraState>, greater<DijkstraState>> pq; int start_x = balls[1].fi, start_y = balls[1].se; pq.push({0, start_x, start_y, 4}); dist[start_x][start_y][4] = 0; auto relaxState = [&] (int x, int y, int d, int newcost) { if (dist[x][y][d] > newcost) { dist[x][y][d] = newcost; pq.push({newcost, x, y, d}); } }; while (!pq.empty()) { int cur_cost = pq.top().cost; int x = pq.top().x, y = pq.top().y, d = pq.top().d; pq.pop(); if (dist[x][y][d] < cur_cost) continue; // Bóng đang cố định if (d == 4) { // Đá bóng đi for (int nxtd = 0; nxtd < 4; ++nxtd) relaxState(x, y, nxtd, cur_cost + b); // Di chuyển bóng đi for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (inside(nx, ny)) relaxState(nx, ny, 4, cur_cost + c); } } // Bóng đang trong tình trạng bị đá else { // Bóng tiếp tục di chuyển { int nx = x + dx[d], ny = y + dy[d]; if (inside(nx, ny)) relaxState(nx, ny, d, cur_cost + a); } // Có người đến nhặt bóng relaxState(x, y, 4, cur_cost + cost[x][y] * c); } } } void solve() { prepare_cost(); dijkstra(); cout << dist[balls[n].fi][balls[n].se][4]; } signed main() { #ifdef NCTHANH freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); init(); solve(); return 0; }