마을 특별비용

N개의 마을이 트리 구조로 연결되어 있으며, 루트는 항상 1번이다. 각 마을 i에는 가중치 w_i가 있으며, 자식 마을의 가중치는 항상 부모 마을의 가중치보다 크다.

각 마을은 "특별 마을" 또는 "일반 마을"로 분류된다. 루트는 항상 특별 마을이다.

• 특별 마을의 비용은 원래 가중치 w_i이다.
• 일반 마을 v의 비용은, v의 가장 가까운 특별 마을 조상 u에 대해 w_v - w_u가 된다.

모든 마을의 비용 합이 최소가 되도록 특별 마을을 선택하는 프로그램을 작성하시오.

입력

첫째 줄에 마을 수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에 N개의 정수 w_1, w_2, ..., w_N이 공백으로 구분되어 주어진다. (1 ≤ w_i ≤ 50,000, 자식 > 부모) 셋째 줄부터 N-1개의 줄에 연결된 두 마을 u v가 공백으로 구분되어 주어진다.

출력

비용 합의 최솟값을 출력한다.

입출력 예시

입력 1

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

출력 1

10

입력 2

4
1 2 3 4
1 2
1 3
1 4

출력 2

7