3341. [USACO20 Jan Gold]Time Is Mooney

【题目描述】

Bessie 正在安排前往 Bovinia 的一次出差，那里有 $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。

【输入格式】

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

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

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

【输出格式】

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

【样例输入】

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×62=24 $哞尼。

【提示】

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Gold 组