1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35

#include <bits/stdc++.h>
using namespace std;

int m[1001], DP[1001][1001];
vector<int> G[1001];

int main() {
	ifstream cin("time.in");
	ofstream cout("time.out");

	int N, M, C;
	cin >> N >> M >> C;
	for (int u = 1; u <= N; ++u) cin >> m[u];
	while (M--) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
	}

	memset(DP, -1, sizeof DP);
	DP[0][1] = 0;
	for (int i = 0; i < 1000; ++i) {
		for (int u = 1; u <= N; ++u) {
			if (DP[i][u] != -1) {
				for (auto& v : G[u]) {
					DP[i + 1][v] = max(DP[i][u] + m[v], DP[i + 1][v]);
				}
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= 1000; ++i) ans = max(DP[i][1] - C * i * i, ans);
	cout << ans << '\n';
}