eolymp
bolt
Try our new interface for solving problems
Problems

Time is Mooney

Time is Mooney

Time limit 1 second
Memory limit 128 MiB

Bessie is conducting a business trip in Bovinia, where there are n cities labeled 1 ... n connected by m one-way roads. Every time Bessie visits city i, Bessie earns m[i] moonies. Starting at city 1 Bessie wants to visit cities to make as much mooney as she can, ending back at city 1. To avoid confusion, m[1] = 0.

Mooving between two cities via a road takes one day. Preparing for the trip is expensive; it costs c * t^2 moonies to travel for t days.

What is the maximum amount of moonies Bessie can make in one trip? Note that it may be optimal for Bessie to visit no cities aside from city 1, in which case the answer would be zero.

Input data

The first line contains three integers n (2n1000), m (1m2000) and c (1c1000). The second line contains the n integers m[1], m[2],..., m[n] (0m[i]1000).

The next m lines each contain two space separated integers a and b (ab) denoting a one-way road from city a to city b.

Output data

Print the maximum amount of moonies Bessie can make in one trip.

Example

The optimal trip is 1231231. Bessie can get 10 + 20 + 10 + 201 * 36 = 24 moonies.

Examples

Input example #1
3 3 1
0 10 20
1 2
2 3
3 1
Output example #1
24
Source 2020 USACO January Gold