問題
YDK鉄道が運営している村中線はN個の駅とN本の線路があり、環状につながっています。i番目とi+1番目の駅を繋ぐ線路を線路iと呼び、線路iを通る際にかかる金額はAiです。ただし、線路Nは、N番目の駅と1番目の駅を繋いでいます。
M人の人がYDK鉄道を利用します。j番目の人は駅Xiから駅Yiに移動します。YDK鉄道の社長であるYDKくんはできるだけぼったくりたいと思っており、金額が高くなるように路線を案内したいです。しかし同じ駅を2回通ってしまうとぼったくりがばれてしまいます。適切にぼったくったとき、YDKくんが得られる金額の総和の最大値を求めてください。
入力
N M A1 A2 ... AN X1 Y1 X2 Y2 . . . XM YM
出力
金額の総和の最大値を出力せよ
制約
2 ≦ N,M ≦ 10^5
1 ≦ Ai ≦ 10^6
1 ≦ Xi,Yi ≦ N
Xi ≠ Yi
入出力例
入力例1
5 3 200 300 500 200 400 2 5 4 3 2 4
出力例1
2900
例えば1番目の乗客について考えます。 2番目の駅から5番目の駅まで、同じ駅を2回通らずに行く方法は二つあります。 2→3→4→5(1000円) 2→1→5(600円) この場合、上のほうが400円多くぼったくれるのでYDKくんは乗客に上の路線を教えます。
入力例2
10 7 689 251 641 162 80 793 259 318 78 616 5 6 8 6 2 10 1 4 10 8 9 6 6 4
出力例
21183