Description

在一个地图上有 $N$ 个地窖（$N \le 200$） ,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径） ，当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

Input Format

从 mine.in 输入数据

$N$ {地窖的个数}

$W_1, W_2,\cdots,W_N$ {每个地窖中的地雷数}

$X_1, Y_1$ {表示从 $X_1$ 可到 $Y_1$}

$X_2, Y_2$

……

$0, 0$ {表示输入结束}

Output Format

向 mine.out 输出数据

$MAX$ {最多挖出的地雷数}

Sample

样例输入1

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

样例输出1

34