Bessie is conducting a business trip in Bovinia, where there are NN (2≤N≤10002≤N≤1000) cities labeled 1…N1…N connected by MM (1≤M≤20001≤M≤2000) one-way roads. Every time Bessie visits city i,i, Bessie earns mimi moonies (0≤mi≤10000≤mi≤1000). 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, m1**=0.m1=0.Mooving between two cities via a road takes one day. Preparing for the trip is expensive; it costs C⋅T2C⋅T2 moonies to travel for TT days (1≤C≤1000**1≤C≤1000).

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 FORMAT (file time.in):

The first line contains three integers NN, MM, and CC.The second line contains the NN integers m1**,m2**,…mNm1,m2,…mN.

The next MM lines each contain two space-separated integers aa and bb (a≠ba≠b) denoting a one-way road from city aa to city bb.

OUTPUT FORMAT (file time.out):

A single line with the answer.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

24

The optimal trip is 1→2→3→1→2→3→1.1→2→3→1→2→3→1. Bessie makes 10+20+10+20−1⋅62**=**2410+20+10+20−1⋅62=24 moonies in total.