Битва за срібло
Піт Хейн був голландським військово-морським офіцером під час Вісімдесятирічної війни між Сполученими Провінціями Нідерландів та Іспанією. Його найвідоміша перемога відбулася у 1628 році біля Куби, коли він захопив "Зільвервлот" ("Срібний флот"), перехопивши іспанські судна, що перевозили срібло з колоній у Північній та Південній Америці до Іспанії. Оскільки деталі цієї морської битви не повністю збережені, наведений опис може містити деякі історичні неточності.
Срібний флот складався з суден, що перевозили срібні монети. Основна стратегія Піта Хейна була проста: відокремити кілька суден від флоту, щоб захопити їх вміст.
Щоб завадити голландцям, іспанці зв'язали всі кораблі у флоті величезними залізними ланцюгами. Кожне судно було прикріплене щонайменше до одного іншого судна, і будь-які два судна з'єднувалися не більше ніж одним ланцюгом. Іспанці також подбали про те, щоб ланцюги не перетиналися, щоб уникнути вузлів. У результаті судна і ланцюги утворили зв'язний плоский граф.
Проте ці заходи лише погіршили становище іспанців. Як досвідчений офіцер, Піт Хейн знав, що найлегше відбуксирувати групу кораблів, якщо кожні два кораблі в ній з'єднані ланцюгом. Він назвав такі групи ланцюговими групами.
Піт Хейн наказав своїм людям відбуксирувати всі кораблі в групі з найбільшою кількістю здобичі, після того як він розірвав їхні зв'язки з рештою флоту кількома точними гарматними пострілами. Загальна здобич у ланцюговій групі - це загальна кількість срібних монет на суднах, що входять до неї.
Срібний флот представлений у вигляді графа: кожна точка позначає судно, а кожна лінія - ланцюг, що з'єднує два судна. Судна, з'єднані пунктирними лініями, утворюють групу з найбільшим сумарним значенням срібних монет. У цьому випадку Піт Хейн здобуває 4500 срібних монет з флоту.
Маючи опис Срібного флоту, знайдіть цінність групи з найбільшою кількістю здобичі (тобто загальну кількість срібних монет на кораблях, що входять до складу групи).
Вхідні дані
Для кожного тесту:
Рядок містить два цілі числа v (2 ≤ v ≤ 450) і e (1 ≤ e ≤ 900) - кількість суден у флоті та кількість ланцюгів.
Наступні v рядків задають
S[1],S[2], ...,S[v]- кількість срібних монет, яке везе судно номер i (1 ≤ i ≤ v). ЧислаS[i]є натуральними, причому 100 ≤S[i]≤ 6000.Далі для кожного ланцюга задано рядок з двох цілих чисел
c[start]іc[end]- номери суден, з'єднаних ланцюгом (1 ≤c[start]<c[end]≤ v).
Кожен флот утворює зв'язний плоский граф.
Вихідні дані
Для кожного тесту вивести в окремому рядку кількість срібних монет, захоплених флотом Піта Хейна.
