Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: atostogos.in

Rezultatų failas: atostogos.out

Jei norite pateikti savo sprendimą - prisijunkite.

Atostogos

Darius planuoja per atostogas pakeliauti. Šalyje yra n miestų, kuriuos jungia m dvipusių kelių, ir iš bet kurio miesto galima nukeliauti į bet kurį kitą. Kiekvieno miesto grožį Darius yra įvertinęs skaičiumi a_i. Darius pasirinko du skirtingus miestus i ir j, kuriuose jis pradės ir pabaigs savo kelionę. Pakeliui jis nori aplankyti kuo gražesnius miestus - tai yra kad mažiausiai gražus miestas iš aplankytų per visą kelionę būtų kiek galima gražesnis.

Dariui parūpo sužinoti - o kokia yra visų galimų kelionių gražumo suma? Tai yra, jei kelionės iš miesto i į miestą j gražumą pažymėsime f(i,j), tai jis norėtų sužinoti sumą \\sum_{i=1}^n\\sum_{j=i+1}^nf(i,j).

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai n ir m - miestų ir kelių skaičius (1\\leqn,m\\leq10^5). Antroje eilutėje yra pateikta n skaičių a_i - miestų gražumo įvertinimai (1\\leqa_i\\leq10^5). Sekančiose m eilučių yra pateikta po du skaičius t_i ir u_i - i-tojo kelio jungiami miestai (1\\leqt_i,u_i\\leqn).

Rezultatas

Išveskite vieną skaičių - sumą visų galimų kelionių gražumų.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
4 3
7 5 3 8
1 3
2 4
1 2
 
24
 
Kelionės iš miesto 1 į miestą 2 gražumas yra 5.
Kelionės iš miesto 1 į miestą 3 gražumas yra 3.
Kelionės iš miesto 1 į miestą 4 gražumas yra 5.
Kelionės iš miesto 2 į miestą 3 gražumas yra 3.
Kelionės iš miesto 2 į miestą 4 gražumas yra 5.
Kelionės iš miesto 3 į miestą 4 gražumas yra 3.
 
5 5
3 4 2 1 8
2 1
2 3
5 4
5 1
1 4
 
19
 
Kelionės iš miesto 1 į miestą 2 gražumas yra 3.
Kelionės iš miesto 1 į miestą 3 gražumas yra 2.
Kelionės iš miesto 1 į miestą 4 gražumas yra 1.
Kelionės iš miesto 1 į miestą 5 gražumas yra 3.
Kelionės iš miesto 2 į miestą 3 gražumas yra 2.
Kelionės iš miesto 2 į miestą 4 gražumas yra 1.
Kelionės iš miesto 2 į miestą 5 gražumas yra 3.
Kelionės iš miesto 3 į miestą 4 gražumas yra 1.
Kelionės iš miesto 3 į miestą 5 gražumas yra 2.
Kelionės iš miesto 4 į miestą 5 gražumas yra 1.