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

Щедрые спонсоры олимпиады, в которой участвуют Хлоя и Владик, разрешили всем участникам выбрать себе приз самостоятельно. Так как близится Новый год, спонсоры решили нарядить новогоднюю елку своими призами.

Они взяли n подарков для участников и на каждом подарке написали его уникальный номер (целое число от 1 до n). Подарок с номером i характеризуется целым числом ai — приятностью подарка. Приятность подарка может быть как положительным, так и отрицательным числом, а так же нулем. Подарок с номером 1 отправился на вершину елки. Все остальные подарки привязываются веревкой к одному из других подарков так, что каждый подарок в итоге оказывается подвешенным к первому подарку, возможно цепочкой из веревок и других подарков. Более формально, подарки формируют корневое дерево из n вершин.

Раздача подарков происходит таким образом: очередной участник подходит к елке, выбирает любой подарок из оставшихся и отрезает веревку, которой был привязан этот подарок. Обратите внимание, что все веревки, которыми другие подарки были привязаны к подарку, выбранному участником, не отрезаются. Таким образом, участник забирает выбранный подарок, а так же все множество подарков, подвешенное к нему, возможно цепочкой из веревок и других подарков.

Наши герои, Хлоя и Владик, поделили между собой на олимпиаде первое место и они, вопреки правилам раздачи подарков, будут выходить за подарком вместе! Чтобы не поссориться, они решили выбрать себе два таких различных подарка, что множества подарков, подвешенное к ним цепочкой из веревок и других подарков, не имеют пересечения. Иначе говоря, не должно быть подарка, который был бы подвешен к подарку Хлои и подарку Владика одновременно. Из всех возможных вариантов они выберут такую пару подарков, что сумма приятностей всех подарков, которые достанутся им после того, как они отрежут веревки, максимальна.

Найдите максимальную сумму приятностей, которую могут забрать себе Хлоя и Владик. Если это по каким-то причинам невозможно, выведите Impossible.

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

В первой строке входного файла записано одно целое число n (1 ≤ n ≤ 2·105) — количество подарков.

В следующей строке записано n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — приятности подарков.

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

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

Если Хлоя и Владик смогут выбрать себе подарки, не поссорившись, выведите одно число — максимальную сумму приятностей, которую они смогут забрать в таком случае.

Иначе выведите строку Impossible.

Примеры
Входные данные
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8
Выходные данные
25
Входные данные
4
1 -5 1 1
1 2
1 4
2 3
Выходные данные
2
Входные данные
1
-1
Выходные данные
Impossible