#include<iostream>
#include<queue>
using namespace std;
int g[1005][1005]={};
struct asdf
{
	int s;
	int t;
	int v;
};
int cnt;
int h[100005]={};
int M[100005]={};
int f[100005]={};
int n,m,c,x,y;

int an;
queue<asdf> q;
int bfs()
{ 
	q.push((asdf){1,0,0});
	for(int i=1;i<=n;i=i+1)
	{
		f[i]=-0x7fffffff; 
	}
	while(!q.empty())
	{
		asdf u=q.front();
		for(int i=1;i<=n;i=i+1)
		{
			if(g[u.s][i]&&u.v+M[i]-c*(u.t+1)*(u.t+1)>f[i]) {q.push((asdf){i,u.t+1,u.v+M[i]});f[i]=u.v+M[i]-c*(u.t+1)*(u.t+1);}
		}
		
		if(q.front().s==1)
		{
			if(q.front().v-c*q.front().t*q.front().t<=an)
			{
				break;
			}else
			{
				an=q.front().v-c*q.front().t*q.front().t;
			}
		}q.pop(); 
	}
}

int main()
{
	
	cin>>n>>m>>c;
	for(int i=1;i<=n;i=i+1) {cin>>M[i];}
	for(int i=1;i<=m;i=i+1) {cin>>x>>y;g[x][y]=1;}
	bfs();
	if(an<=0)
	{
		cout<<0;
	}else
	{
		cout<<an;
	}
	
	return 0;
}