Bil Gheiț, patronul Companiei Macrosoft, vă pune la dispoziție o matrice cu n linii, numerotate de la 1 la n și n coloane, numerotate de la 1 la n, care memorează numere naturale. Un drum în matrice care pornește de la poziția (1,1) și se termină la poziția (n,n) este constituit din componente adiacente două câte două pe linii și coloane. Costul drumului este egal cu suma costurilor componentelor prin care trece drumul.

Cerința

Determinați costul minim al unui drum care pornește de la poziția (1,1) și se termină la poziția (n,n) și domnul Bil Gheiț vă va angaja imediat la compania sa pe post de fochist.

Date de intrare

Pentru toate testele, matricea se va genera aleator. Se citesc de la tastatură mai întâi numerele naturale n, X, Y, Z, T, iar apoi exact n numere naturale reprezentând prima linie din matrice. Restul elementelor se vor genera după formula: a[i][j] = 1 + (a[i-1][j-1] * X + a[i-1][j] * Y + a[i-1][j+1] * Z) % T, i=2..n, j=1..n. Se observă că unele elemente din formulă pot fi 0, de exemplu, atunci când se calculează valoarea lui a[2,1] care depinde de a[1, 0].

Date de ieșire

Programul va afișa la ecran, ca să vadă și Bil, suma minimă a unui drum de la (1,1) la (n,n).

Restricții și precizări

• 1 ≤ n ≤ 1500
• 1 ≤ X, Y, Z, T ≤ 500
• 1 ≤ a[i,j] ≤ 500, pentru orice i=1..n, j=1..n

Exemplu

Intrare

8 21 23 57 31
253 416 101 476 248 159 387 209 

Ieșire

446

#include <bits/stdc++.h>

using namespace std;

int n, X, Y, Z, T, inf = 1000000001;
int a[1501][1501];
int d[1501][1501];

bool inmat(int i, int j){
    return i >= 1 && i <= n && j >= 1 && j <= n;
}

int di[]={0,-1,1,0};
int dj[]={-1,0,0,1};

void lee(int i, int j){
    priority_queue<pair<int, pair<int, int>>,vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int, int>>>> Q;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            d[i][j] = inf;
    d[i][j] = a[i][j];
    Q.push({a[i][j],{i, j}});
    while(!Q.empty()){
        pair<int, pair<int, int>> x = Q.top();
        for(int i = 0; i <= 3; ++i){
            int inou = x.second.first + di[i];
            int jnou = x.second.second + dj[i];
            if(inmat(inou, jnou) && d[x.second.first][x.second.second] + a[inou][jnou] < d[inou][jnou])
                d[inou][jnou] = d[x.second.first][x.second.second] + a[inou][jnou], Q.push({d[inou][jnou], {inou, jnou}});
        }
        Q.pop();
    }
    cout << d[n][n];
}

int main(){
    cin >> n >> X >> Y >> Z >> T;
    for(int i = 1; i <= n; ++i)
        cin >> a[1][i];
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
             a[i][j] = 1 + (a[i-1][j-1] * X + a[i-1][j] * Y + a[i-1][j+1] * Z) % T;
    lee(1, 1);
    return 0;
}