#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,c;
vector<ll>v[1005];
ll f[1005],g[1005],t[1005];
bool flag[1001];
queue<ll>q;
int main()
{
	scanf("%lld%lld%lld",&n,&m,&c);
	memset(f,-0x3f,sizeof(f));
	fill(g,g+n+1,INT_MAX/c);
	for(int i=1;i<=n;i++)scanf("%lld",&t[i]);
	for(int i=1;i<=m;i++)
	{
		ll x,y;
		scanf("%lld%lld",&x,&y);
		v[x].push_back(y);
	}
	flag[1]=1;
	g[1]=0;
	f[1]=0;
	q.push(1);
	while(!q.empty())
	{
		ll h=q.front();
		flag[h]=0;
		q.pop();
		for(ll i:v[h])
		{
			if(f[h]+t[i]-c*(g[h]+1)*(g[h]+1)>f[i]-c*g[i]*g[i])
			{
				f[i]=f[h]+t[i];
				g[i]=g[h]+1;
				if(!flag[i])q.push(i),flag[i]=1;
			}
		}
	}
	cout<<max(0LL,f[1]-c*g[1]*g[1]);
	return 0;
}

原题