Description

On a map, there are n cellars (n ≤ 200), each containing a certain number of mines. The connecting paths between the cellars are given, and all paths are unidirectional. It is guaranteed that the paths always go from a smaller-numbered cellar to a larger-numbered cellar, and there are no cycles (i.e., it is impossible to start from a cellar, traverse through a series of cellars, and return to the original cellar). A person can start digging for mines from any cellar and then proceed along one of the connecting paths. The digging ends when no further connections are available. Design a mine-digging strategy to maximize the total number of mines collected.

Input Format

• The first line: the number of cellars.
• The second line: the number of mines in each cellar, listed in order.
• The following lines: each line contains x_i y_i, indicating a path from x_i to y_i. The input ends with a line 0 0.

Output Format

k_1-k_2-…-k_v    // The sequence of cellars to dig in order to collect the maximum number of mines.

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

3-4-5-6
34