Đất nước Byteland có \(N\) thành phố được đánh số từ \(1\) đến \(N\). Các thành phố này được kết nối bởi \(M\) con đường một chiều. Trí chuẩn bị một kế hoạch du lịch dài ngày ở Byteland. Mỗi lần Trí đến thăm thành phố \(i\), độ sảng khoái của cậu sẽ tăng lên \(m_i\) đơn vị. Để di chuyển giữa hai thành phố bất kỳ, Trí phải bỏ ra đúng một ngày. Nếu chuyến du lịch của cậu dài tổng cộng \(T\) ngày, cậu phải hy sinh \(C\cdot T^2\) đơn vị của độ sảng khoái.

Trí sẽ xuất phát ở thành phố \(1\) và có độ sảng khoái bằng \(0\) ở thời điểm khởi hành. Bạn hãy lập trình giúp Trí tìm một chu trình du lịch (kết thúc tại chính thành phố \(1\)) để độ sảng khoái sau cùng của Trí là lớn nhất có thể nhé. Lưu ý rằng trường hợp cậu không thăm thành phố nào (để nhận lại độ sảng khoái bằng \(0\)) vẫn được tính là hợp lệ. Để tránh nhầm lẫn, dữ liệu luôn đảm bảo \(m_1=0\).

Input

Dòng đầu chứa ba số nguyên dương \(N\), \(M\), và \(C\) (\(1\leq N\leq 1000\), \(1\leq M\leq 2000\), \(1\leq C\leq 1000\)).

Dòng tiếp theo chứa \(N\) số nguyên \(m_1\), \(m_2\),..., \(m_N\) \((0\leq m_i\leq 1000)\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) \((a\ne b)\) thể hiện một con đường một chiều nối thành phố a với thành phố b.

Output

In ra một số nguyên là tổng độ sảng khoái lớn nhất có thể của Trí.

Ví dụ

Sample input

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

Sample output

24

Giải thích

Lộ trình du lịch tối ưu của Trí là \(1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\). Tổng độ sảng khoái sau cùng của cậu là \(10+20+10+20-1\cdot 6^2=24\).