题目描述

地图上有n个地窖，编号1至n，第i个地窖有一定数量的地雷。地窖之间有单向道路，所有道路都从较小编号指向较大编号。

你可以从任意地窖开始，沿道路选择一条路径，挖出沿途各地窖的地雷；到达没有出路的地窖时结束。请给出地雷总数最多的方案。

输入格式

第一行整数n。第二行n个整数，表示各地窖的地雷数。接下来每行两个整数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≤n≤200；每个地窖的地雷数在0至10000之间；每条道路满足1≤x<y≤n，没有重复道路。