Бесси проводит своё путешествие в Бовинии, где имеется n городов, помеченных числами 1 ... n, соединённых m однонаправленными дорогами. Каждый раз, когда Бесси посещает город i, Бесси зарабатывает mi денег. Начиная с города 1, Бесси хочет посетить города так, чтобы заработать как можно больше денег и вернуться город 1 (m1 = 0).

Перемещение между двумя городами по дороге занимает один день. Во время путешествия приходиться тратиться. Чтобы путешествовать t дней, следует потратить c * t2 денег.

Какое максимальное количество денег Бесси может заработать в одном путешествии? Заметим, что для Бесси может оказаться оптимальным не посещать никакой город кроме первого и в этом случае ответ будет 0.

Входные данные

Первая строка содержит три целых числа n (2 ≤ n ≤ 1000), m (1 ≤ m ≤ 2000) и c (1 ≤ c ≤ 1000). Вторая строка содержит n целых чисел m1, m2,..., mn (0 ≤ mi ≤ 1000).

Каждая из следующих m строк содержит два разделённых пробелом целых числа a и b (a ≠ b), обозначающих однонаправленную дорогу из города a в город b.

Выходные данные

Выведите максимальное количество денег, которое Бесси может заработать в одном путешествии.

Пример

Оптимальное путешествие таково 1 → 2 → 3 → 1 → 2 → 3 → 1. Бесси заработает 10 + 20 + 10 + 20 − 1 * 36 = 24 денег.