Time is Mooney.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

FrankHG

Problem type

Allowed languages

C, C#, C++, Java, Pascal, Python, VB

Bessie está realizando un viaje de negocios en Bovinia, donde hay $N$ ~N~ ciudades etiquetadas $1 \ldots N$ ~1 \ldots N~ conectadas por $M$ ~M~ carreteras de sentido único. Cada vez que Bessie visita la ciudad $i$ ~i~, Bessie gana $m_i$ ~m_i~ monedas. Comenzando en la ciudad $1$ ~1~, Bessie quiere visitar ciudades de forma que pueda ganar la mayor cantidad de dinero posible, terminando de nuevo en la ciudad $1$ ~1~. Para evitar confusión, $m_1 = 0$ ~m_1 = 0~.

Moverse entre dos ciudades a través de una carretera toma un día. Prepararse para el viaje es caro; viajar $T$ ~T~ días cuesta $C * T^2$ ~C * T^2~.

¿Cuál es la cantidad máxima de dinero que Bessie puede hacer en un viaje? Tenga en cuenta que puede ser óptimo que Bessie no visite ninguna ciudad aparte de la ciudad $1$ ~1~, en cuyo caso la respuesta sería cero.

Entrada

La primera línea contiene tres enteros $N$ ~N~, $M$ ~M~, y $C$ ~C~.
La segunda línea contiene el $N$ ~N~ enteros $m_1, m_2, \ldots, m_N$ ~m_1, m_2, \ldots, m_N~.
Las siguientes $M$ ~M~ líneas contienen dos enteros separados por espacios $a$ ~a~ y $b$ ~b~ $(a \neq b)$ ~(a \neq b)~ que denota un camino de un solo sentido desde la ciudad $a$ ~a~ hasta la ciudad $b$ ~b~.