Problem 1. Time is Mooney

USACO 2020 January Contest, Gold

Bessie 正在安排前往牛尼亚的一次出差，那里有 $N$（$2\le N\le 1000$）个编号为 $1\ldots N$ 的城市，由 $M$ （$1\le M\le 2000$）条单向的道路连接。Bessie 每次访问城市 $i$ 都可以赚到 $m_i$ 哞尼（$0\le m_i\le 1000$）。从城市 1 出发，Bessie 想要赚到尽可能多的哞尼，最后回到城市 1。为了避免争议，$m_1=0$。

沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行 $T$ 天需要花费 $C\cdot T^2$ 哞尼（$1\le C\le 1000$）。

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

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

输入的第一行包含三个整数$N$、$M$ 和 $C$。

第二行包含 $N$ 个整数 $m_1,m_2,\ldots m_N$。

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

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

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

输入样例：

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

输出样例：

24

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

供题：Richard Peng，Mark Gordon