Sjekira

Ο Mirko έχει βαρεθεί την αγχωτική δουλειά του CEO σε μια γνωστή πολυεθνική εταιρεία λογισμικού. Με μια μεγάλη χρηματική αποζημίωση πολλών εκατομμυρίων δολαρίων, αποφάσισε να ζήσει μια απλή ζωή και να μετακομίσει στο Gorski Kotar. Ωστόσο, οι χειμώνες στο απομακρυσμένο χωριό που μόλις μετακόμισε είναι δύσκολοι. Κανένας από τους γείτονές του δεν γεννήθηκε μετά τον Β' Παγκόσμιο Πόλεμο και έτσι προορίζεται να κόβει μόνος του καυσόξυλα.

Σήμερα, πρόκειται να αρχίσει να κόβει ως ένα σημείο τον πρώτο του κορμό. Πριν τον κόψει, βάζει ετικέτες στα μέρη του κορμού που είναι αρκετά μικρά για να χωρέσουν στο τζάκι και μετρά τη σκληρότητά τους.

Ο Mirko είναι προγραμματιστής, οπότε παρατηρεί ότι τα μέρη και οι μεταξύ τους συνδέσεις σχηματίζουν ένα γράφημα δέντρου.

Η ζημιά στο τσεκούρι του, που προκύπτει από το κόψιμο μιας σύνδεσης στον κορμό, είναι ίση με το άθροισμα των μέγιστων σκληροτήτων στα δύο συνδεδεμένα μέρη του κορμού, που σχηματίζονται με το κόψιμο της σύνδεσης.

Ο Mirko έχει μόνο ένα τσεκούρι, οπότε θέλει η συνολική ζημιά να είναι όσο το δυνατόν μικρότερη. Θέλει να μάθει την ελάχιστη συνολική ζημιά στο τσεκούρι, αν κόψει ολόκληρο τον κορμό σε μεμονωμένα μέρη, που χωράνε στο τζάκι.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο n, τον αριθμό των τμημάτων στα οποία θα κοπεί ο κορμός. Τα μέρη επισημαίνονται με ακέραιους αριθμούς από το 1 έως το ~n~.

Η δεύτερη γραμμή περιέχει n ακέραιους ~t_i\;(1 \le t_i \le 10^9)~. Ο αριθμός ~t_i~ είναι η σκληρότητα του τμήματος με την ένδειξη ~i~.

Κάθε μία από τις ακόλουθες ~n - 1~ γραμμές περιέχει δύο ακέραιους αριθμούς ~x~ και ~y\;(1 \le x, y \le n)~ – οι ετικέτες των τμημάτων που είναι άμεσα συνδεδεμένα.

Έξοδος

Περιλαμβάνει την ελάχιστη συνολική ζημιά μετά από ~n - 1~ κοπές.

Βαθμολογία

Σε όλα τα υποπροβλήματα ισχύει ότι ~1 \le n \le 100\,000~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 10~
2	10	Τα μέρη ~i~ και ~i+1\;(1 \le i \le n - 1)~ συνδέονται απευθείας.
3	30	~1 \le n \le 1\,000~
4	60	~1 \le n \le 100\,000~

Παραδείγματα

input

3
1 2 3
1 2
2 3

output

8

Επεξήγηση του 1ου παραδείγματος:

Υπάρχουν δύο τρόποι για να κόψετε αυτόν τον κορμό. Μπορεί πρώτα να κοπεί η σύνδεση ~(1,\;2)~, η οποία προκαλεί ζημιά ~1 + 3 = 4~ και έπειτα να κόψετε τη σύνδεση ~(2,\;3)~, η οποία προκαλεί ζημιά ~2 + 3 = 5~. Η συνολική ζημιά είναι 9 σε αυτή την περίπτωση.

Διαφορετικά, μπορεί πρώτα να κόψετε τη σύνδεση ~(2,\;3)~ και μετά τη σύνδεση ~(1,\;2)~. Η συνολική ζημιά σε αυτήν την περίπτωση είναι ~(2 + 3) + (1 + 2) = 8~.

input

4
2 2 3 2
1 3
3 2
4 3

output

15

input

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

output

26