#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const int di[4] = {0, 0, -1, 1}; const int dj[4] = {-1, 1, 0, 0}; int h, w, n; long long a, b, c; long long cost[501][501], f[501][501][5]; pair<int, int> p[100000]; inline void CalculateCost() { priority_queue<pair<long long, pair<int, int>>> pq; int x, y, nxt_x, nxt_y; long long z; for (int i = 0; i <= h; ++i) { fill_n(cost[i], w + 1, 1e18); } for (int i = 0; i < n; ++i) { cost[p[i].first][p[i].second] = 0; pq.push({0, p[i]}); } while (!pq.empty()) { z = -pq.top().first; x = pq.top().second.first; y = pq.top().second.second; pq.pop(); if (cost[x][y] != z) { continue; } for (int i = 0; i < 4; ++i) { nxt_x = x + di[i]; nxt_y = y + dj[i]; if (0 <= nxt_x && nxt_x <= h && 0 <= nxt_y && nxt_y <= w && cost[nxt_x][nxt_y] > cost[x][y] + c) { cost[nxt_x][nxt_y] = cost[x][y] + c; pq.push({-cost[nxt_x][nxt_y], {nxt_x, nxt_y}}); } } } } inline void CalculateResult() { long long v; int x, y, z, nxt_x, nxt_y; priority_queue<pair<long long, array<int, 3>>> pq; for (int i = 0; i <= h; ++i) { for (int j = 0; j <= w; ++j) { fill_n(f[i][j], 5, 1e18); } } f[p[0].first][p[0].second][4] = 0; pq.push({0, {p[0].first, p[0].second, 4}}); while (!pq.empty()) { v = -pq.top().first; x = pq.top().second[0]; y = pq.top().second[1]; z = pq.top().second[2]; pq.pop(); if (v != f[x][y][z]) { continue; } if (z == 4) { for (int i = 0; i < 4; ++i) { nxt_x = x + di[i]; nxt_y = y + dj[i]; if (0 <= nxt_x && nxt_x <= h && 0 <= nxt_y && nxt_y <= w) { if (f[nxt_x][nxt_y][i] > f[x][y][z] + a + b) { f[nxt_x][nxt_y][i] = f[x][y][z] + a + b; pq.push({-f[nxt_x][nxt_y][i], {nxt_x, nxt_y, i}}); } if (f[nxt_x][nxt_y][z] > f[x][y][z] + c) { f[nxt_x][nxt_y][z] = f[x][y][z] + c; pq.push({-f[nxt_x][nxt_y][z], {nxt_x, nxt_y, z}}); } } } continue; } if (f[x][y][4] > f[x][y][z] + cost[x][y]) { f[x][y][4] = f[x][y][z] + cost[x][y]; pq.push({-f[x][y][4], {x, y, 4}}); } nxt_x = x + di[z]; nxt_y = y + dj[z]; if (0 <= nxt_x && nxt_x <= h && 0 <= nxt_y && nxt_y <= w && f[nxt_x][nxt_y][z] > f[x][y][z] + a) { f[nxt_x][nxt_y][z] = f[x][y][z] + a; pq.push({-f[nxt_x][nxt_y][z], {nxt_x, nxt_y, z}}); } } } int main() { setup(); cin >> h >> w >> a >> b >> c >> n; for (int i = 0; i < n; ++i) { cin >> p[i].first >> p[i].second; } CalculateCost(); CalculateResult(); // for (int i = 0; i <= h; ++i) // { // for (int j = 0; j <= w; ++j) // { // cout << cost[i][j] << " "; // } // cout << "\n"; // } // cout << "\n"; // for (int i = 0; i <= h; ++i) // { // for (int j = 0; j <= w; ++j) // { // cout << f[i][j][4] << " "; // } // cout << "\n"; // } cout << f[p[n - 1].first][p[n - 1].second][4]; return 0; }