Час муньги#9602
Беssі перебуває у діловій поїздці в Бовінії, де є міст, пронумерованих від до і з'єднаних дорогами з одностороннім рухом. Кожного разу, коли Беssі відвідує місто , вона отримує m_i муні. Починаючи з міста , Беssі хоче відвідувати міста так, щоб заробити якомога більше муні, і в кінці вона повинна повернутися до міста . Для ясності будемо вважати, що m_1 = 0.
Переміщення між двома містами по дорозі займає один день. Підготовка до поїздки коштує дорого: подорож тривалістю днів коштує c \cdot t^2 муні.
Яку максимальну кількість муні може заробити Беssі за одну поїздку? Зауважте, що Беssі може виявитися вигідніше не відвідувати жодних міст, крім міста , і в такому випадку відповідь буде рівна нулю.
У першому рядку містяться три цілих числа: n~(2 \le n \le 1000), m~(1 \le m \le 2000) та c~(1 \le c \le 1000).
У другому рядку містяться цілих чисел m_1, m_2, \ldots, m_n~(0 \le m_i \le 1000).
У наступних рядках містяться по два розділених пробілом цілих числа та b~(a \ne b), що позначають одностороннью дорогу з міста до міста .
Виведіть максимальну кількість муні, яку Беssі може заробити за одну поїздку.
Оптимальний маршрут має вигляд 1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1. Беssі отримує 10 + 20 + 10 + 20 = 60 муні і витрачає 1 \cdot 6^2 = 36 муні на подорож. Таким чином, її підсумковий прибуток становить .
Приклад 1