题目背景

原题为 P6005 [USACO20JAN] Time is Mooney G

题目描述

Gooby 正在艾美莉卡出差，那里有 $N$（$2 \leq N \leq 1000$）个编号为 $1 \ldots N$ 的城市，由 $M$（$1 \leq M \leq 2000$）条单向的道路连接。Gooby 每次访问城市 $i$ 都可以赚到 $m_i$ 刀乐（$0 \leq m_i \leq 1000$）。从城市 $1$ 出发，Gooby 想要赚到尽可能多的刀乐，最后回到城市 $1$。为了避免争议，$m_1=0$。

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

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

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

24

说明/提示

最优的旅行方案是 $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to1$。Gooby 总共赚到了 $10+20+10+20-1 \times 6^2=24$ 刀乐。

数据范围

对于 $100\%$ 的数据，$2 \leq N \leq 1000,$ $1 \leq M \leq 2000$, $1 \leq C \leq 1000,$$m_1 = 0,0 \leq m_i \leq 1000$