Bessie đang đi công tác tại Bovinia, nơi có \(N\) thành phố (\(2\le N\le 1000\)) được đánh số \(1\ldots N\) và nối với nhau bằng \(M\) con đường một chiều (\(1\le M\le 2000\)). Mỗi lần ghé thăm thành phố \(i\), Bessie kiếm được \(m_i\) mooney (\(0\le m_i\le 1000\)). Khởi hành từ thành phố \(1\), Bessie muốn ghé thăm các thành phố để kiếm được nhiều mooney nhất có thể rồi kết thúc hành trình tại thành phố \(1\). Để tránh nhầm lẫn, \(m_1=0\).

Di chuyển giữa hai thành phố qua một con đường mất một ngày. Việc chuẩn bị cho chuyến đi rất tốn kém; một hành trình dài \(T\) ngày tiêu tốn \(C\cdot T^2\) mooney (\(1\le C\le 1000\)).

Số mooney lớn nhất Bessie có thể kiếm được trong một chuyến đi là bao nhiêu? Lưu ý rằng phương án tối ưu có thể là Bessie không ghé thăm thành phố nào ngoài thành phố \(1\); trong trường hợp đó, đáp án là \(0\).

Dữ liệu vào

Dữ liệu vào được đọc từ tệp time.in.

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(C\).

Dòng thứ hai chứa \(N\) số nguyên \(m_1,m_2,\ldots,m_N\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) (\(a\neq b\)), cách nhau bởi dấu cách, biểu thị một con đường một chiều từ thành phố \(a\) đến thành phố \(b\).

Dữ liệu ra

Ghi ra tệp time.out một dòng chứa đáp án.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

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

24

Nguồn

• Kỳ thi: USACO 2020 January Contest, Gold
• Tên bài: Time is Mooney
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=993
• Tác giả đề: Richard Peng và Mark Gordon