Problem H
Bygge bro

I gamle dage, længe inden LTH blev grundlagt, boede der $M$ kærestepar på Söderåsen. Hver af de $2M$ personer boede et helt antal meter fra starten af åsen, desværre ikke på samme sted som sin kæreste.

Söderåsen kan modelleres som en følge af positive heltal $H$, hvor det $i$te tal angiver højden over havet $i$ meter fra åsens begyndelse. At gå en meter langs åsen tager lige så mange minutter som højdeforskellen plus $1$. Det tager altså $|H_ i - H_{i+1}| + 1$ minutter at komme fra position $i$ til position $i+1$.

Söderåsens beboere blev efterhånden trætte af at skulle gå i dagevis for at besøge deres kærester, så de besluttede at bygge en bro for at forbinde to positioner på åsen. En bro kunne bygges mellem position $i$ og $j$, hvis $j > i$, $H_ i = H_ j$ og $H_ k < H_ i$ for hvert heltal $k$ med $i< k< j$. Sådan en bro ville tillade folk at gå fra position $i$ til $j$ på $j - i$ minutter.

Desværre havde de gamle skåninger ikke adgang til hverken regnemaskiner eller kurser i algoritmik, så  placeringen af deres bro var måske ikke optimal. Den bedste bro ville minimere summen af tiden for alle kærestepar for at nå hinanden. Hvis den bedste bro var blevet bygget, hvad havde denne sum været?

Indlæsning

Første linje indeholder to heltal $N$ og $M$, hvor $2 \leq N\leq 200\, 000$ og $1\leq M \leq 200\, 000$, henholdsvis længden af åsen i meter og antallet at kærestepar på åsen.

Anden linje indeholder $N$ heltal $H_1 \dots H_ N$, hvor $0 \leq H_ i \leq 10^6$, som angiver åsens højder.

Hver af de næste $M$ linjer består af to heltal $a_ i,b_ i\in \{ 1,\ldots , N\} $ med $a_ i \neq b_ i$,som angiver positionerne for de to personer i det $i$te kærestepar.

Det er garanteret, at der findes mindst et sted at bygge en bro.

Udskrift

Skriv et enkelt heltal, den mindst mulige sum af afstande mellem alle kærestepar, når en optimal bro er bygget.

Pointsætning

Din løsning udsættes for en række af test i forskellige testgrupper. For at få point for en gruppe skal du klare alle test i gruppen.

Forklaring af eksemplerne

I eksempel 1 er der kun en mulig bro, mellem de to positioner med højde 4. Denne bro reducerer afstanden mellem de to personer fra $10$ til $7$.

5 1
3 4 1 3 4
1 4

7

13 4
4 5 4 3 1 4 3 1 4 5 4 4 5
8 6
4 9
1 10
11 13

32