eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сражение за серебро

Сражение за серебро

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Пит Хейн был голландским военно-морским офицером во время Восьмидесятилетней войны между Соединенными Провинциями Нидерландов и Испании. Его самая известная победа заключалась в захвате в 1628 году около Кубы "Зильвервлота" ("Серебряный флот"), где он перехватил ряд испанских судов, перевозивших серебро из испанских колоний в Северной и Южной Америке в Испанию. Детали об этом знаменитом военно-морском сражении отрывочны, поэтому приведенное ниже описание может содержать некоторые исторические неточности.

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

Пытаясь помешать голландцам выполнить этот план, испанцы связали все корабли в своем флоте, используя огромные железные цепи. Каждое судно во флоте было прикреплено по меньшей мере к одному другому судну. Любые два судна соединялись не более чем одной цепью. И испанцы убедились, что цепи не пересекаются, иначе они могли бы завязаться в узел. Как результат, судна и цепи образовали связный плоский граф.

Тем не менее, испанские превентивные меры только ухудшили их положение. Как опытный военно-морской офицер, Пит Хейн знал, что отбуксировать группу кораблей легче всего, если каждые два корабля в ней будут соединены цепью. Он назвал такие группы цепными группами.

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

prb7014

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

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

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

Для каждого теста:

  • Строка содержит два целых числа v (2v450) и e (1e900) - число суден во флоте и число цепей.

  • Следующие v строк задают S[1], S[2], ..., S[v] - количество серебряных монет, которое везет судно номер i (1iv). Числа S[i] являются натуральными, причем 100S[i]6000.

  • Далее для каждой цепи задана строка из двух целых чисел c[start] и c[end] - номера суден, соединенных цепью (1c[start] < c[end]v).

Каждый флот образует связный плоский граф.

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

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

prb7014.gif

Пример

Входные данные #1
4 6
100
5000
1000
2000
1 2
1 3
1 4
2 3
2 4
3 4
6 8
1500
1000
100
2000
500
300
1 2
1 3
1 4
2 4
3 5
4 5
4 6
5 6
Выходные данные #1
8100
4500
Источник 2013 ACM North Western European Regional Contest (NWERC), Ноябрь 24, Задача B