Сражение за серебро
Пит Хейн был голландским военно-морским офицером во время Восьмидесятилетней войны между Соединенными Провинциями Нидерландов и Испании. Его самая известная победа заключалась в захвате в 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).
Каждый флот образует связный плоский граф.
Выходные данные
Для каждого теста вывести в отдельной строке количество серебряных монет, захваченных флотом Пита Хейна.
