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

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

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

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

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

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

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

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

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

• Строка содержит два целых числа v (2 ≤ v ≤ 450) и e (1 ≤ e ≤ 900) - число суден во флоте и число цепей.
• Следующие v строк задают S1, S2, ..., Sv - количество серебряных монет, которое везет судно номер i (1 ≤ i ≤ v). Числа Si являются натуральными, причем 100 ≤ Si ≤ 6000.
• Далее для каждой цепи задана строка из двух целых чисел cstart и cend - номера суден, соединенных цепью (1 ≤ cstart < cend ≤ v).

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

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

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