問題文
兔子非常喜欢金钱。
兔子决定在某个城市进行散步。然而,每条街道只能走一次,但可以从任意城市出发。
街 i 有的钱是 D_i 日元, 兔子想尽可能多地获取金钱。
请计算兔子能获取的最大金额。
不过,城市共有 N 个,道路共有 K 条, 道路 i 连接着城市 X_i和 按字典顺序比较 Y_i,而且道路是双向通行的。
入力
输入是按以下格式从标准输入给出的。
N K D_1 D_2 : D_N X_1 Y_1 X_2 Y_2 : : X_K Y_K
- 1 行包含一个整数 N 和 按字典顺序比较 K。 表示
- 下一步 N 行包含了城市i 的金钱数 D_i 。 表示
- 以及下一行 K 行包含X_i 和 按字典顺序比较Y_i。 表示
出力
应按以下格式输出到标准输出。 新道路建成后所有可能城市之间的最短路线长度之和,直至
兔子能够获得的最大金额,请在一行中输出。
但是,答案可能 32 不适合比特整数类型。
制約
- 1≦N≦50
- 1≦K≦50
- 1≦D_i≦1,000,000,000
- 1≦X_i, Y_i≦N
- X_i≠Y_i
- 已保证不存在相同的道路。
- 可能的散步路线是2,000,000不超过通行道。
部分点
这个问题设有部分分数。
1≦N,K≦10如果对满足条件的测试用例全部答对,将给予50分。
如果对剩下的所有数据集全部答对,将给予50分。
入力例1
6 6 1 2 3 4 5 7 1 2 1 3 1 6 2 4 3 4 4 5
出力例1
20
街 6 从……出发,6→1→3→4→5 按……顺序走将会得到 7+1+3+4+5=20一个圆。
入力例2
4 2 1 10 5 6 1 2 3 4
出力例2
11
入力例3
5 4 2 3 5 6 7 1 3 1 4 2 4 4 5
出力例3
20
问题文承担者:E869120