Time is Mooney#9602
Bessie is on a business trip in Bovinia, where there are cities labeled through , connected by one-way roads. Every time Bessie visits city , she earns m_i moonies. Starting from city , Bessie wants to visit cities in order to earn as many moonies as possible, and she must eventually return to city . To avoid confusion, m_1 = 0.
Moving between two cities along a road takes one day. Preparing for the trip is expensive: traveling for days costs c \cdot t^2 moonies.
What is the maximum amount of moonies Bessie can earn on one trip? Note that it may be optimal for Bessie not to visit any city other than city 1, in which case the answer is zero.
The first line contains three integers n~(2 \le n \le 1000), m~(1 \le m \le 2000), and c~(1 \le c \le 1000).
The second line contains integers m_1, m_2, \ldots, m_n~(0 \le m_i \le 1000).
The next lines each contain two space-separated integers and b~(a \ne b), denoting a one-way road from city to city .
Print the maximum amount of moonies Bessie can earn on one trip.
The optimal trip is 1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1. Bessie earns 10 + 20 + 10 + 20 = 60 moonies and spends 1 \cdot 6^2 = 36 moonies on travel, for a total profit of .
Example 1