Время муньги
Бесси проводит своё путешествие в Бовинии, где имеется n городов, помеченных числами 1 ... n, соединённых m однонаправленными дорогами. Каждый раз, когда Бесси посещает город i, Бесси зарабатывает m[i] денег. Начиная с города 1, Бесси хочет посетить города так, чтобы заработать как можно больше денег и вернуться город 1 (m[1] = 0).
Перемещение между двумя городами по дороге занимает один день. Во время путешествия приходиться тратиться. Чтобы путешествовать t дней, следует потратить c * t^2 денег.
Какое максимальное количество денег Бесси может заработать в одном путешествии? Заметим, что для Бесси может оказаться оптимальным не посещать никакой город кроме первого и в этом случае ответ будет 0.
Входные данные
Первая строка содержит три целых числа n (2 ≤ n ≤ 1000), m (1 ≤ m ≤ 2000) и c (1 ≤ c ≤ 1000). Вторая строка содержит n целых чисел m[1], m[2],..., m[n] (0 ≤ m[i] ≤ 1000).
Каждая из следующих m строк содержит два разделённых пробелом целых числа a и b (a ≠ b), обозначающих однонаправленную дорогу из города a в город b.
Выходные данные
Выведите максимальное количество денег, которое Бесси может заработать в одном путешествии.
Пример
Оптимальное путешествие таково 1 → 2 → 3 → 1 → 2 → 3 → 1. Бесси заработает 10 + 20 + 10 + 20 − 1 * 36 = 24 денег.