题目描述

有 $n$ 个地窖，编号为 $1$ 到 $n$，第 $i$ 个地窖中有若干枚地雷。地窖之间有若干条单向通道，每条通道都从编号较小的地窖通向编号较大的地窖。

可以从任意一个地窖出发，并沿通道选择一条路径前进。经过一个地窖时，可以获得其中的全部地雷。请找出一条路径，使获得的地雷总数最大。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个地窖中的地雷数。

接下来若干行，每行包含两个整数 $x,y$，表示存在一条从地窖 $x$ 通向地窖 $y$ 的单向通道。

输入以一行 0 0 结束。

输出格式

第一行输出获得最多地雷时经过的地窖编号，相邻编号之间用连字符 - 分隔。

第二行输出最多可以获得的地雷总数。

样例

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

数据范围与提示

• $1 \le n \le 200$
• 对于每条通道，$1 \le x < y \le n$