struct Node {
    int x, y;
    ll d;
    bool operator< (const Node &t) const {
        return d > t.d;
    }
};
void solve() {
    ll n, A, B, C;
    cin >> n >> A >> B >> C;

    vector e(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> e[i][j];

    const ll inf = 1e18;
    vector d(2, vector<ll>(n + 1, inf)); d[0][1] = 0;
    priority_queue<Node> q;
    q.push({0, 1, 0});
    vector visi(2, vector(n + 1, false));
    while (q.size()) {
        auto [x, y, D] = q.top(); q.pop();
        if (visi[x][y]) continue;
        visi[x][y] = 1;
        for (int ny = 1; ny <= n; ny++) {
            ll w = x == 0 ? A * e[y][ny] : B * e[y][ny] + C;
            if (d[x][ny] > d[x][y] + w) {
                d[x][ny] = d[x][y] + w;
                q.push({x, ny, d[x][ny]});
            }
        }
        if (x == 0) {
            if (d[1][y] > d[0][y]) {
                d[1][y] = d[0][y];
                q.push({1, y, d[1][y]});
            }
        }
    }
    cout << d[1][n] << '\n';
}