AT_s8pc_1_c お金の街 (The Money Town)
题目描述
兔子很喜欢钱。
兔子决定在某个城市里散步。但是，由于时间的关系，不能走两次相同的街道，从哪个城市出发都可以。
街ii钱被D_iD
i
日元，兔子尽可能想收钱。
求能拿到的钱的最大值。
但，街NN个，道路KK个，道路ii街X_iX
i
和“Y_iY”
i
正在打结。另外,道路可以双向通行。
输入格式
输入是以下形式从标准输入被提供的。
$N$$K$
$D_1$
$D_2$
：
$D_N$
$X_1$$Y_1$
$X_2$$Y_2$
：：
$X_K$$Y_K$
11行提供整数NN和KK。
下面的NN行，街ii有的钱D_iD
i
被给予。
在下一行KK中，X_iX
i
和“Y_iY”
i
被给予。
输出格式
输出以以下形式进行标准输出。
把兔子能得到的最大值输出一行。
但是，回答3232位整数型不容纳的可能性。
说明/提示
#### 约束
1≤N≤501≤N≤50
1≤K≤501≤K≤50
1≤D_i≤1,000,0001≤D
i
≤1,000,000,000
1≤X_i,1≤X
i
,Y_i≤NY
i
≤N
≠Y_iX
i
_;
=Y
i
保证同一条路不存在
可能的散步路径是2000,0002,000,000,000街道以下。
#### 部分点
这个问题设定了部分点。
如果对满足1≤N，K≤101≤N，K≤10的所有测试案件都正确，则给予50分。
如果对所有剩余数据集合都正确，则给出50分。
#### Sample Explanation 1
从街66出发，按6→1→3→4→56→1→3→4→5的顺序走的话，可以得到7+1+3+4+5=207+1+3+4+5=20日元。