Bessie está realizando un viaje de negocios en Bovinia, donde hay ~N ( 2 \leq N \leq 1000 )~ ciudades etiquetadas ~1 ... N~ conectadas por ~M ( 1 \leq M \leq 2000 )~ carreteras de sentido único. Cada vez que Bessie visita la ciudad ~i~, Bessie gana ~m_i~ monedas ~( 0 \leq m_i \leq 1000 )~. Comenzando en la ciudad ~1~, Bessie quiere visitar ciudades de forma que pueda ganar la mayor cantidad de dinero posible, terminando de nuevo en la ciudad ~1~. Para evitar confusión, ~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~ días ~( 1 \leq C \leq 1000)~ cuesta ~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~, en cuyo caso la respuesta sería cero.

Entrada

La primera línea contiene tres enteros ~N~, ~M~, y ~C~.

La segunda línea contiene el ~N~ enteros ~m_1, m_2, ... m_N~.

Las siguientes ~M~ líneas contienen dos enteros separados por espacios ~a~ y ~b~ ~( a \neq b )~ que denota un camino de un solo sentido desde la ciudad ~a~ hasta la ciudad ~b~.

Salida

Una sola línea con la respuesta.

Ejemplo de Entrada

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

Ejemplo de Salida

24

El viaje óptimo es ~1 \rarr 2 \rarr 3 \rarr 1 \rarr 2 \rarr 3 \rarr 1~.

Bessie obtiene ~10 + 20 + 10 + 20 - 1 * 6^2 = 24~ como ganancia total.