Problem 22171 --挖地雷

22171: 挖地雷

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 125  Solved: 53
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][184kb]

Description

      在一个地图上有N个地窖(N<=200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。

Input

第一行一个整数n表示有n个地窖

第二行有n个整数表示每个地窖的地雷数

以下有若干行,每行有两个数x,y表示x可以到y,保证x小于y。

最后一行有两个0,表示输入结束

Output

第一行输出挖地雷的顺序。

第二行为最多挖出的地雷数

Sample Input

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

Sample Output

3-4-5-6
34

HINT

Source

[Submit][Status]