Problem description

Przygotowywanie paczek z zadaniami na obóz to czynność bardzo przyjemna i satysfakcjonująca, choć często wymaga dużo pracy i zarwania kilku nocy. Jednakże po tej ciekawszej części, składającej się z pisania wzorcówek, heurystyk, brutów i generowania testów, przychodzi czas na tą mniej ciekawą, ale niestety też ważną część – pisanie treści zadania.

Chomin i Marcel, podobnie jak na kilku ostatnich obozach, postanowili że treści zadań każdego dnia będą spójne tematycznie, a na trzeci dzień obozu przypadła tematyka Kadra (kilka historyjek z prawdziwymi bohaterami, które jakoś nawiążą do ich cech itp.). Niestety, Artur nie przepada za bardzo za pisaniem treści, a do tego za jedno z zadań zabrał się późno w nocy, bezpośrednio przed dniem gdy zadanie ma się ukazać na zawodach. Co gorsza, musi on napisać treść do zadania w którym dane jest drzewo z wagami na wierzchołkach, usuwanie krawędzi generuje pewien koszt związany z tymi wagami, a celem zawodnika jest zminimalizowanie tego kosztu. Artur totalnie się załamał, gdyż nie wiedział jak w tej treści odnieść się do kadry. Dlatego też postanowił, że nie będzie się wysilał – napisze treść, która jest krótka (co z pewnego punktu widzenia mu nie wyszło), nie ma duszy, a motyw kadry jest do niej wciśnięty na siłę.

…

Marcel dostał na urodziny swój wymarzony graf – spójny, nieskierowany, mający N wierzchołków, N − 1 krawędzi i wagi na wierzchołkach. Jest on przeszczęśliwy, gdyż kocha grafy tego typu. Teraz postanowił, że będzie kolejno usuwał z niego krawędzie. Koszt usunięcia krawędzi (u,v) będzie wynosił tyle, ile wynosi maksymalna waga wierzchołka w spójnej zawierającej wierzchołek u oraz maksymalna waga wierzchołka w spójnej zawierającej wierzchołek v (bierzemy pod uwagę spójne po usunięciu tej krawędzi).

Marcel zastanawia się jaki jest minimalny koszt usunięcia wszystkich krawędzi. Czy jesteś w stanie mu pomóc?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N.

W drugim wierszu wejścia znajduje się N oddzielonych pojedynczymi spacjami liczb w₁, …, w_N, oznaczających wagi na kolejnych wierzchołkach.

Kolejne N − 1 zawiera po dwie oddzielone spacją liczby całkowite u i v, oznaczające że w grafie istnieje krawędź między tymi właśnie wierzchołkami.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą minimalny koszt usunięcia wszystkich krawędzi przez Marcela.

Ograniczenia

0 ≤ N ≤ 100 000, 1 ≤ w_i ≤ 10⁹, 1 ≤ u, v ≤ N, podany na wejściu graf jest drzewem.

Przykład

3
1 2 3
1 2
2 3

8

4
2 2 3 2
1 3
3 2
4 3

15

5
5 2 3 1 4
2 1
3 1
2 4
2 5

26