Час муньги
Бессі вирушає в подорож по Бовінії, де розташовані 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 грошей.