题目描述

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

沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行 $T$ 天需要花费 $C \times T^2$ 哞尼（$1 \leq C \leq 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 \to 2 \to 3 \to 1 \to 2 \to 3 \to1$。Bessie 总共赚到了 $10+20+10+20-1 \times 6^2=24$ 哞尼。