002 - ARUMAKAN-IO

問題

YDK鉄道が運営している村中線はN個の駅とN本の線路があり、環状につながっています。i番目とi+1番目の駅を繋ぐ線路を線路iと呼び、線路iを通る際にかかる金額はA_iです。ただし、線路Nは、N番目の駅と1番目の駅を繋いでいます。

M人の人がYDK鉄道を利用します。j番目の人は駅X_iから駅Y_iに移動します。YDK鉄道の社長であるYDKくんはできるだけぼったくりたいと思っており、金額が高くなるように路線を案内したいです。しかし同じ駅を2回通ってしまうとぼったくりがばれてしまいます。適切にぼったくったとき、YDKくんが得られる金額の総和の最大値を求めてください。

入力

N M
A1 A2 ... AN
X1 Y1
X2 Y2
.
.
.
XM YM

出力

金額の総和の最大値を出力せよ

制約

2 ≦ N,M ≦ 10^5
1 ≦ A_i ≦ 10^6
1 ≦ X_i,Y_i ≦ N
X_i ≠ Y_i

入出力例

入力例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