#include <bits/stdc++.h>

using namespace std;
ifstream fin ("time.in");
ofstream fout ("time.out");
int n, m, c, x, y, a[1005][1005], val[1005], maxx;
vector <int> v[1005];

int main()
{
    fin >> n >> m >> c;
    for(int i=1;i<=n;i++)
        fin >> val[i];

    for(int i=1;i<=m;i++)
    {
        fin >> x >> y;
        v[x].push_back(y);
    }

    for(int i=0;i<=n;i++)
        a[0][i]=-1;
    a[0][1]=0;

    for(int i=0;i<=1000;i++)
    {
        for(int j=1;j<=n;j++)
            a[i+1][j]=-1;

        for(int j=1;j<=n;j++)
            if(a[i][j]!=-1)
                for(auto it:v[j])
                    a[i+1][it]=max(a[i+1][it], a[i][j]+val[it]);
    }

    for(int i=0;i<=1000;i++)
        maxx=max(maxx, a[i][1]-i*i*c);
    fout << maxx;
    return 0;
}