F. Шоколадное веселье
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы и Боба есть дерево (неориентированный связный ацикличный граф). В i-й вершине дерева лежит ai шоколадок. Сперва ребята выбирают себе стартовые вершины (Алиса выбирает первой) и забирают себе все шоколадки, которые там лежат.

Затем Алиса и Боб ходят по очереди, на каждом ходу выбирая одну вершину и забирая все лежащие там шоколадки. Чтобы разнообразить процесс, они договорились, что каждый из них может выбирать только среди вершин, которые являются соседними по отношению к выбранной этим игроком вершиной на предыдущем ходу. Более того, можно выбирать только вершины, не выбранные до этого никем другим.

Если в какой-то момент времени один из игроков не может сделать ход, он просто ожидает, пока другой игрок сделает все свои ходы. Процесс заканчивается, когда ни Алиса, ни Боб не могут больше сделать ни одного хода.

Поскольку Алиса и Боб — большие сладкоежки, они хотят собрать как можно больше шоколадок. Однако они ещё и друзья, поэтому их волнует только суммарное количество шоколадок, которое они соберут вместе. Найдите это значение, если ребята действуют оптимально.

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

В первой строке входных данных записано число n (2 ≤ n ≤ 100 000) — количество вершин в дереве.

Во второй строке записаны n целых чисел ai (1 ≤ ai ≤ 109), i-е из которых определяет количество шоколадок в вершине с номером i.

Далее следует n - 1 строка, описывающая дерево. В каждой из них записаны два целых числа ui и vi (1 ≤ ui, vi ≤ n) — индексы вершин, соединённых i-м ребром.

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

Выведите, сколько шоколадок смогут собрать Алиса и Боб, если они будут действовать оптимально.

Примеры
Входные данные
9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
Выходные данные
25
Входные данные
2
20 10
1 2
Выходные данные
30
Примечание

В первом примере Алиса начнёт в вершине 9, а Боб в вершине 8. Затем Алиса сделает ход в вершину 1, и Боб будет вынужден остаться на месте. Алиса сделает ход в вершину 7, и игра закончится.

Во втором примере они сразу выберут две вершины и заберут их них все шоколадки.