滑雪

题目描述

AtCoder 滑雪场有 $N$ 个场地,称为场地 $1$,场地 $2$,$\ldots$,场地 $N$。场地 $i$ 的海拔为 $H_i$。

有 $M$ 条双向连接两个场地的滑雪道。第 $i$ 条滑雪道 $(1 \le i \le M)$ 连接场地 $U_i$ 和场地 $V_i$。可以通过若干条滑雪道往返于任意两个场地之间。

高桥只能通过滑雪道在场间移动。每次经过一条滑雪道,他的幸福值都会变化。具体来说,当他从场地 $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$

输出格式

输出答案。

样例

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

3

若高桥走路线场地 $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$,这是能达到的最大值。

2 1
0 10
1 2

0

不移动时幸福值最大。

数据范围

• $2 \le N \le 2\times 10^5$
• $N-1 \le M \le \min( 2\times 10^5,\frac{N(N-1)}{2})$
• $0 \le H_i \le 10^8$ $(1 \le i \le N)$
• $1 \le U_i \lt V_i \le N$ $(1 \le i \le M)$
• 当 $i \neq j$ 时,$(U_i,V_i) \neq (U_j, V_j)$。
• 输入中的所有值均为整数。
• 可以通过若干条滑雪道往返于任意两个场地之间。