时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H在今年的高考中考取了理想的大学，但大学的学费不菲，于是他想利用这个暑假边旅行边打工挣学费。

　　C国共有 \(N（2≤N≤1000）\)个编号为 \(1..N\) 的城市，由 \(M（1≤M≤2000）\)条单向的道路连接。小H每次访问到城市 \(i\) 都可以赚到 \(C_i\)元RMB\(（0≤Ci≤1000）\)。从城市 1 出发，小H想要赚到尽可能多的RMB，最后回到城市1。为了避免歧义，规定\(C_1=0\)。

　　沿着两个城市之间的道路移动需要消耗一天的时间。出行的准备工作十分费钱，旅行 \(T\) 天需要花费 \(R×T^2\) 元的RMB\(（1≤R≤1000）\)。

　　那么小H 在一次旅行中最多可以赚到多少RMB？注意有可能最优方案是小H不访问城市 \(1\) 之外的任何城市，在这种情况下结果应当为 0。

【输入格式】

　　第一行包含三个整数 \(N、M\) 和 \(R\)。
　　第二行包含 \(N\) 个整数 \(C_1, C_2, …, C_N（C_1\)一定为 \(0）\)。
　　以下 \(M\) 行每行包含两个空格分隔的整数 \(a\) 和 \(b（a≠b）\)，表示从城市 \(a\) 到城市 \(b\) 的一条单向道路。

【输出格式】

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

【输入输出样例1】

　Input

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

　Output

24

【样例1解释】

　　最优的旅行方案是：1→2→3→1→2→3→1。小H总共赚到了 10+20+10+20-1×62=24 元RMB。

【输入输出样例2】

　Input

10 11 3
0 16 34 42 190 43 131 28 31 189
8 9
4 5
10 5
2 3
5 1
6 7
7 8
3 4
5 6
1 2
9 10

　Output

639

【数据限制】

　　- 对于 \(100\%\) 的数据，有 \(1≤N≤1000\)。

【来源】

　　Mr.he