E

#include <bits/stdc++.h>

using namespace std;

#define ll     long long

int main()
{
    ll int n, a, b, c;
    cin>>n>>a>>b>>c;

    vector<vector<ll int>> D(n, vector<ll int> (n));
    for(int i=0; i<n; i++)  for(int j=0; j<n; j++)  cin>>D[i][j];

    array<ll int, 2> tmp;
    tmp[0] = 1e18;
    tmp[1] = 1e18;

    vector<array<ll int, 2>> dist(n, tmp);
    dist[0][0] = 0;
    dist[0][1] = 0;

    set<array<ll int, 3>> sp;
    sp.insert({dist[0][0], 0, 0});

    while(sp.size())
    {
        auto [pr, u, s] = *sp.begin();
        sp.erase(sp.begin());

        for(int v=0; v<n; v++)
        {
            if(s == 0)
            {
                if(dist[v][0] > pr+D[u][v]*a)
                {
                    dist[v][0] = pr+D[u][v]*a;
                    sp.insert({dist[v][0], v, 0});
                }

                if(dist[v][1] > pr + D[u][v]*b + c)
                {
                    dist[v][1] = pr + D[u][v]*b + c;
                    sp.insert({dist[v][1], v, 1});
                }
            }
            else
            {
                if(dist[v][1] > pr + D[u][v]*b + c)
                {
                    dist[v][1] = pr + D[u][v]*b + c;
                    sp.insert({dist[v][1], v, 1});
                }
            }
        }
    }

    cout<<min(dist[n-1][0], dist[n-1][1])<<"\n";
}