### 问题描述 小齐正在进行一次商务之旅，他需要拜访 $Bovinia$ 国内的 $N$ 个城市，这些城市标有编号 $1 \ldots N$，城市之间有 $M$ 条单向道路相连。每次小齐访问第 $i$ 个城市，他可以获得 $m_i$ 个 $moonies$。小齐从城市 $1$ 出发，希望尽可能多地拜访其他城市，最终回到城市 $1$。为了避免混淆，定义 $m_1=0$。 通过道路在两个城市之间移动需要一天的时间。在准备旅行时，需要支付 $C \cdot T^2$ 个 $moonies$ 来旅行 $T$ 天。 在一次旅行中，小齐能够获得的最大 $moonies$ 数量是多少？请注意，有时对小齐来说，除了访问城市 $1$ 外，不访问其他城市可能是最优选择，此时答案为零。 ### 输入格式 第一行包含三个整数 $N$，$M$，$C$。 第二行包含 $N$ 个整数 $m_1, m_2, \ldots, m_N$。 接下来的 $M$ 行，每行包含两个整数 $a$ 和 $b$，表示从城市 $a$ 到城市 $b$ 的单向道路（$a \neq b$）。 ### 输出格式 输出一个整数，表示小齐在一次旅行中能够获得的最大 $moonies$ 数量。 ### 样例输入 ``` 3 3 1 0 10 20 1 2 2 3 3 1 ``` ### 样例输出 ``` 24 ``` ### 评测数据规模 $1 \leq M \leq 2000$，$0 \leq m_i \leq 1000$，$1 \leq C \leq 1000$。