Cow Trip Profit Maximization

Bessie is planning a business trip to Bullonia, which has \(N\) cities numbered from \(1\) to \(N\) and \(M\) one‐way roads connecting them. Every time Bessie visits city \(i\) she earns \(m_i\) moo-nies, with the constraint that \(m_1 = 0\). Starting from city \(1\), she wishes to earn as many moo-nies as possible and then return to city \(1\) at the end of her trip.

Traveling along any road takes one day. However, preparation costs are high: a trip lasting \(T\) days costs \(C \times T^2\) moo-nies. In other words, if the trip lasts \(T\) days, the penalty is given by:

\( C \times T^2 \)

Determine the maximum profit Bessie can achieve. Note that if the best strategy is to not leave city \(1\) (i.e. take \(T=0\) days), the answer should be \(0\).

inputFormat

The first line contains three integers: \(N\), \(M\), and \(C\) \( (2 \leq N \leq 1000,\ 1 \leq M \leq 2000,\ 1 \leq C \leq 1000)\).

The second line contains \(N\) integers: \(m_1, m_2, \ldots, m_N\) \( (0 \leq m_i \leq 1000)\) with the guarantee that \(m_1 = 0\).

Each of the next \(M\) lines contains two integers \(u\) and \(v\), indicating a one-way road from city \(u\) to city \(v\).

outputFormat

Output a single integer representing the maximum profit Bessie can earn on her trip.

sample

3 3 1
0 1 2
1 2
2 3
3 1

0