Bessie 正在安排前往牛尼亚的一次出差，那里有N（2≤N≤1000）个编号为 1…N 的城市，由 M （1≤M≤2000）条单向的道路连接。Bessie 每次访问城市 i 都可以赚到 mi 哞尼（0≤m$_i$≤1000）。从城市 1 出发，Bessie 想要赚到尽可能多的哞尼，最后回到城市 1。为了避免争议，m$_1$=0。沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行T 天需要花费 C⋅T$^2$ 哞尼（1≤C≤1000）。

Bessie 在一次出差中最多可以赚到多少哞尼？注意有可能最优方案是 Bessie 不访问城市 1 之外的任何城市，在这种情况下结果应当为 0。

输入格式（文件名：time.in）：

输入的第一行包含三个整数N、M 和 C。第二行包含 N 个整数m$_1$,m$_2$,…m$_N$。

以下 M 行每行包含两个空格分隔的整数 a 和 b（a≠b），表示从城市 a 到城市 b 的一条单向道路。

输出格式（文件名：time.out）：

输出一行，包含所求的答案。

输入样例：

3 3 1
0 10 20
1 2
2 3
3 1

输出样例：

24

最优的旅行方案是 1→2→3→1→2→3→1。Bessie 总共赚到了 10+20+10+20−1⋅6$^2$=24 哞尼。