Беси проводит своё путешествие в Бовинии, где имеется \(N\) городов
(\(2\le N\le 1000\)) городов помеченных числами \(1\ldots N\), соединённых
\(M\) (\(1\le M\le 2000\)) однонаправленными дорогами.
Каждый раз, когда Беси посещает город \(i,\) Беси зарабатывает \(m_i\) денег.
(\(0\le m_i\le 1000\)). Начиная с города 1, Беси хочет так посетить города,
чтобы заработать как можно больше денег и вернуться город 1.
\(m_1=0.\)
Перемещение между двумя городами по дороге занимает один день.
Во время путешествия приходиться тратиться. Чтобы путешествовать \(T\) дней
требуется потратить \(C\cdot T^2\) денег, где (\(1\le C\le 1000\)).
Какое максимальное количество денег Беси может заработать в одном путешествии?
Заметим, что для Беси может оказаться оптимальным не посещать никакой город
кроме первого и в этом случае ответ будет 0.
ФОРМАТ ВВОДА (файл time.in):
Первая строка содержит три целых числа
\(N\),
\(M\), и
\(C\).
Вторая строка содержит \(N\) целых чисел \(m_1,m_2,\ldots m_N\).
Каждая из следующих \(M\) строк содержит два разделённых пробелом целых числа
\(a\) и \(b\) \(a\neq b\)) обозначающих однонаправленную дорогу из города \(a\) в город \(b\).
ФОРМАТ ВЫВОДА (файл time.out):
Единственная строка с ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
0 10 20
1 2
2 3
3 1
|
24
|