当前没有测试数据。

E - 滑雪

分数：500分

问题描述

AtCoder滑雪场有$N$个开放空间，分别称为空间1，空间2，……，空间$N$。第$i$个空间的海拔高度为$H_i$。

有$M$条连接两个空间的双向坡道。第$i$条坡道（$1 \leq i \leq M$）连接空间$U_i$和空间$V_i$。可以通过一些坡道在任意两个空间之间旅行。

Takahashi只能通过使用坡道在空间之间旅行。每次他进入一条坡道，他的“幸福指数”都会改变。具体而言，当他通过直接连接它们的坡道从空间$X$到空间$Y$时，他的幸福指数会按以下方式改变。

• 如果空间$X$的海拔高度严格高于空间$Y$的海拔高度，则幸福指数会增加它们之间的差值：$H_X-H_Y$。
• 如果空间$X$的海拔高度严格低于空间$Y$的海拔高度，则幸福指数会减少它们之间差值的两倍：$2(H_Y-H_X)$。
• 如果空间$X$的海拔高度等于空间$Y$的海拔高度，则幸福指数不变。

幸福指数可能为负值。

初始时，Takahashi在空间1，并且他的幸福指数为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)$。
• 输入中的所有值都是整数。
• 可以通过一些坡道从任意两个空间之间旅行。

输入

输入从标准输入中按以下格式给出：

$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

如果Takahashi选择经过的路线为空间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

通过不动而最大化幸福指数。