Time is Mooney

题目描述:

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

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

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

输入格式:

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

第二行包含 N 个整数 m1,m2,…mN。

以下 M 行每行包含两个空格分隔的整数 a和 b（a≠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⋅6²=24 哞尼。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2020 JAN Gold