Bajtocia szykuje się do wystrzelenia pierwszej rakiety w kosmos. Bajtazar jest jednym z pracowników programu kosmicznego i odpowiada za proces wsiadania astronautów do rakiety. Wnętrze rakiety składa się z $n$ kajut połączonych dwukierunkowymi korytarzami w taki sposób, że pomiędzy każdymi dwiema kajutami można przejść na dokładnie jeden sposób (jeśli nie będziemy po drodze zawracać). Przejście każdego korytarza zajmuje jedną sekundę bajtocką. Kajuty są ponumerowane od $1$ do $n$. Wejście do rakiety prowadzi do kajuty numer $1$.

Do rakiety wsiadać będzie $n$ kosmonautów, również ponumerowanych od $1$ do $n$. Dla każdego $1 \le i \le n$ kosmonauta numer $i$ mieszkać będzie w kajucie numer $i$. Kosmonauci wchodzą do rakiety jeden po drugim w odstępach jednosekundowych (w sekundach bajtockich) i idą najkrótszą drogą do swojej kajuty. Kosmonauta numer $i$ po dotarciu do swojej kajuty zaczyna rozkładać swoje rzeczy, co zajmuje mu dokładnie $a_i$ sekund bajtockich.

Kolejność wchodzenia mieszkańców na statek musi być taka, by nikt nie musiał przechodzić przez kajutę, w której znajduje się już jej mieszkaniec (niezależnie od tego, czy ów mieszkaniec zakończył już rozpakowywanie, czy jeszcze nie).

Zadaniem Bajtazara jest takie zaplanowanie procesu wsiadania do rakiety, by przebiegł on jak najszybciej, to znaczy by pomiędzy wejściem pierwszego kosmonauty na statek a momentem, w którym wszyscy kosmonauci zakończą rozpakowywanie, upłynęło jak najmniej czasu.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita $n$ ($2 \le n \le 500\ 000$) oznaczająca liczbę kosmonautów i liczbę kajut. Drugi wiersz zawiera ciąg $n$ liczb całkowitych $a_i$ ($1 \le a_i \le 10^9$). Liczba $a_i$ określa, ile czasu potrzebuje kosmonauta numer $i$ na rozpakowanie się. Kolejne $n - 1$ wierszy opisuje układ kajut na statku. Każdy z nich zawiera dwie liczby całkowite $a$ i $b$ ($1 \le a, b \le n$), które oznaczają, że kajuty o numerach $a$ i $b$ są połączone bezpośrednim korytarzem.

Wyjście

Wypisz minimalny czas potrzebny wszystkim kosmonautom na wejście na statek i rozlokowanie się w kajutach.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

7