Битва за срібло#7014

Битва за срібло

1 секунда

128 мегабайтів

Складна

Піт Хейн був голландським військово-морським офіцером під час Вісімдесятирічної війни між Сполученими Провінціями Нідерландів та Іспанією. Його найвідоміша перемога відбулася у 1628 році біля Куби, коли він захопив "Зільвервлот" ("Срібний флот"), перехопивши іспанські судна, що перевозили срібло з колоній у Північній та Південній Америці до Іспанії. Оскільки деталі цієї морської битви не повністю збережені, наведений опис може містити деякі історичні неточності.

Срібний флот складався з суден, що перевозили срібні монети. Основна стратегія Піта Хейна була проста: відокремити кілька суден від флоту, щоб захопити їх вміст.

Щоб завадити голландцям, іспанці зв'язали всі кораблі у флоті величезними залізними ланцюгами. Кожне судно було прикріплене щонайменше до одного іншого судна, і будь-які два судна з'єднувалися не більше ніж одним ланцюгом. Іспанці також подбали про те, щоб ланцюги не перетиналися, щоб уникнути вузлів. У результаті судна і ланцюги утворили зв'язний плоский граф.

Проте ці заходи лише погіршили становище іспанців. Як досвідчений офіцер, Піт Хейн знав, що найлегше відбуксирувати групу кораблів, якщо кожні два кораблі в ній з'єднані ланцюгом. Він назвав такі групи ланцюговими групами.

Піт Хейн наказав своїм людям відбуксирувати всі кораблі в групі з найбільшою кількістю здобичі, після того як він розірвав їхні зв'язки з рештою флоту кількома точними гарматними пострілами. Загальна здобич у ланцюговій групі - це загальна кількість срібних монет на суднах, що входять до неї.

Срібний флот представлений у вигляді графа: кожна точка позначає судно, а кожна лінія - ланцюг, що з'єднує два судна. Судна, з'єднані пунктирними лініями, утворюють групу з найбільшим сумарним значенням срібних монет. У цьому випадку Піт Хейн здобуває $4500$ срібних монет з флоту.

Маючи опис Срібного флоту, знайдіть цінність групи з найбільшою кількістю здобичі (тобто загальну кількість срібних монет на кораблях, що входять до складу групи).

Вхідні дані

Для кожного тесту:

Рядок містить два цілі числа $v$ ( $2 \leq v \leq 450$ 2 \le v \le 450) і $e$ ( $1 \leq e \leq 900$ 1 \le e \le 900) - кількість суден у флоті та кількість ланцюгів.
Наступні $v$ рядків задають $S_{1}, S_{2}, \dots, S_{v}$ S_1, S_2, \ldots, S_v - кількість срібних монет, яке везе судно номер $i$ ( $1 \leq i \leq v$ 1 \le i \le v). Числа $S_{i}$ S_i є натуральними, причому $100 \leq S_{i} \leq 6000$ 100 \le S_i \le 6000.
Далі для кожного ланцюга задано рядок з двох цілих чисел $c_{s t a r t}$ c_{start} і $c_{e n d}$ c_{end} - номери суден, з'єднаних ланцюгом ( $1 \leq c_{s t a r t} < c_{e n d} \leq v$ 1 \le c_{start} < c_{end} \le v).

Кожен флот утворює зв'язний плоский граф.

Вихідні дані

Для кожного тесту вивести в окремому рядку кількість срібних монет, захоплених флотом Піта Хейна.

Приклади

Приклад 1