N个点编号为1~N，（2≤N≤1000）由M（1≤M≤2000）条单向道路连接，访问点i可获得mi(mi<=1000)元，源点为1，获得尽可能多的钱返回源点，m1=0.两点间耗费时间为1天，游览T天花费C*T²元（1≤C≤1000）。

输入的第一行包含三个整数N、M 和 C。
第二行包含 N 个整数 m1,m2,…mN。
以下 M 行每行包含两个空格分隔的整数 a 和 b（a≠b），表示从城市 a 到城市b 的一条单向道路。

输出一行，包含所求的答案。