대학의 80 주년 기념하기 위해 파티를 계획하고 있다. 이 대학은 트리 형태의 상하 구조로 이뤄어져 있다. 즉 총장을 루트로 상하로 직속관계가 이루어져 있다.

모든 사람이 즐거운 파티를 위해 총장은 직원들이 직속 관계에 있는 사람을 파티에 참석시키지 않기로 하였다. 인사과는 모든 직원의 친밀도를 평가 점수표를 가지고 있다. 직속 상관이 파티에 참석하지 않도록 하면서 친밀도의 총합을 최대로 하는 것이다.

입력

• 첫 라인은 인원 수 N (1 <= N <= 6000)이고
• 다음 n 라인은 친밀도 ( -128 에서 127 까지의 정수)의 점수가 주어지고 다음 N-1 줄까지 L k 형태로 주어진다. k 는 L 의 직속 상관을 의미한다. 0 0 은 입력의 끝이다.

출력

입출력 예

입력

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

출력

5

보충 설명

출처:Ural State University Internal Contest October'2000 Students Session