暂无测试数据。

题目描述

有个公司要举行一场晚会。 为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司 （上司的上司，上司的上司的上司……都可以邀请）。每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

输入格式

第$\red {1}$行一个整数$\red {N（1<=N<=6000）}$表示公司的人数。 接下来$\red {N}$行每行一个整数。第$\red {i}$行的数表示第$\red {i}$个人的气氛值$\red {x(-128≤x≤127)}$。 接下来每行两个整数$\red {L，K}$。表示第$\red {K}$个人是第$\red {L}$个人的上司。

输出格式

一个数，最大的气氛值和。

样例

输入样例

7              

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

输出样例

5