题目描述

AtCoder スキー場には広場 $1$ 、広場 $2$ 、$\ldots$ 、広場 $N$ の $N$ 個の広場があり、広場 $i$ の標高は $H_i$ です。 また、$2$ つの広場を双方向に結ぶ $M$ 本の坂があり、$i$ $(1\ \leq\ i\ \leq\ M)$ 本目の坂は広場 $U_i$ と広場 $V_i$ を双方向に結んでいます。どの $2$ つの広場の間もいくつかの坂を使って移動することができます。

高橋君は坂を使うことによってのみ広場の間を移動でき、坂を通るごとに楽しさが変化します。具体的には広場 $X$ と広場 $Y$ を直接結ぶ坂を使って広場 $X$ から広場 $Y$ まで移動したとき次のように楽しさが変化します。

• 広場 $X$ が広場 $Y$ より標高が真に高い場合、その標高差、すなわち $H_X-H_Y$ だけ楽しさが増加する。
• 広場 $X$ が広場 $Y$ より標高が真に低い場合、その標高差の $2$ 倍、すなわち $2(H_Y-H_X)$ だけ楽しさが減少する。
• 広場 $X$ と広場 $Y$ の標高が等しい場合、楽しさは変化しない。

楽しさは負の値になることもあります。

最初、高橋君は広場 $1$ におり、楽しさは $0$ です。 高橋君はいくつかの坂（ $0$ 本でも良い）を移動した後に好きな広場で行動を終えることができるとしたとき、行動を終えた時点の高橋君の楽しさとしてありうる最大の値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $H_1$ $H_2$ $\ldots$ $H_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

答えを出力せよ。

题目大意

AtCoder 滑雪场有 N 个场地，称为场地1、场地2、…、场地N。场地i的高度为 H_i。有 M 个斜坡双向连接两个空间。第i个斜坡（1≤i≤M）连接场地 U_i 和场地 V_i。可以通过一些斜坡在任意两个空间之间滑行。

高桥只能通过斜坡在场地之间穿行。每次他穿过斜坡，他的幸福感都会改变。具体来说，当他使用直接连接两个场地的斜坡从X斜坡到Y斜坡时，他的幸福感会发生如下变化：

• 如果场地X的高度严格高于场地Y的高度，那么幸福感会增加 (H_X-H_Y)。

• 如果场地X的海拔高度严格低于场地Y的海拔高度，幸福感会降低 2*(H_Y-H_X)。

• 如果场地X的高度等于场地Y的高度，幸福感不会改变。

Tips: 幸福感可能是一个负值。

起初，高桥在场地1号，他的幸福感是0。他可以通过任何数量的斜坡（可能为零）、在任何空间结束。输出他最大可能的幸福感。

翻译 By @凤凰工作室

4 4
10 8 12 5
1 2
1 3
2 3
3 4

3

2 1
0 10
1 2

0

提示

制約

• $2\ \leq\ N\ \leq\ 2\times\ 10^5$
• $ N-1\ \leq\ M\ \leq\ \min(\ 2\times\ 10^5,\frac{N(N-1)}{2}) $
• $0\ \leq\ H_i\leq\ 10^8$ $(1\ \leq\ i\ \leq\ N)$
• $1\ \leq\ U_i\ <\ V_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ M)$
• $i\ \neq\ j$ ならば $(U_i,V_i)\ \neq\ (U_j,\ V_j)$
• 入力はすべて整数である。
• どの $2$ つの広場の間もいくつかの坂を使って移動することができる。

Sample Explanation 1

広場 $1$ $\to$ 広場 $3$ $\to$ 広場 $4$ と移動したとき、楽しさは次のように変化します。 - 広場 $1$（標高 $10$ ）から坂を使って広場 $3$（標高 $12$ ）へ移動します。楽しさは $2\times\ (12-10)=4$ だけ減少し、$0-4=-4$ になります。 - 広場 $3$（標高 $12$ ）から坂を使って広場 $4$（標高 $5$ ）へ移動します。楽しさは $12-5=7$ だけ増加し、$-4+7=3$ になります。 ここで行動を終了したとき終了時の楽しさは $3$ であり、このときが最大となります。

Sample Explanation 2

一度も移動を行わない時、楽しさが最大となります。