Skiing

题目描述

AtCoder 滑雪场有 $N$ 个广场，编号为 $1,2,\ldots,N$。广场 $i$ 的海拔为 $H_i$。

滑雪场中有 $M$ 条双向坡道，第 $i$ 条坡道连接广场 $U_i$ 和广场 $V_i$。保证任意两个广场之间都可以通过若干条坡道互相到达。

高桥只能通过坡道在广场之间移动。每经过一条直接连接广场 $X$ 和广场 $Y$ 的坡道，从 $X$ 移动到 $Y$ 时，他的快乐值会按如下规则变化：

• 如果广场 $X$ 的海拔严格高于广场 $Y$，快乐值增加 $H_X-H_Y$；
• 如果广场 $X$ 的海拔严格低于广场 $Y$，快乐值减少 $2(H_Y-H_X)$；
• 如果两个广场海拔相同，快乐值不变。

快乐值可以为负数。

初始时，高桥位于广场 $1$，快乐值为 $0$。他可以经过任意条坡道，也可以一条都不经过，并且可以在任意广场结束行动。请问结束行动时，快乐值最大可能是多少。

输入格式

输入从标准输入给出，格式如下：

N M
H_1 H_2 ... H_N
U_1 V_1
U_2 V_2
...
U_M V_M

输出格式

输出一个整数，表示结束行动时快乐值的最大可能值。

数据范围

• $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 U_i < V_i \le N$
• 若 $i\ne j$，则 $(U_i,V_i)\ne (U_j,V_j)$。
• 输入均为整数。
• 任意两个广场之间都可以通过若干条坡道互相到达。

样例

样例输入 1

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

样例输出 1

3

样例输入 2

2 1
0 10
1 2

样例输出 2

0

样例说明

样例 1 中，若沿着 $1\to 3\to 4$ 移动：

• 从海拔 $10$ 的广场 $1$ 到海拔 $12$ 的广场 $3$，快乐值减少 $2\times(12-10)=4$，变为 $-4$；
• 从海拔 $12$ 的广场 $3$ 到海拔 $5$ 的广场 $4$，快乐值增加 $12-5=7$，变为 $3$。

此时结束行动可以得到最大快乐值 $3$。

样例 2 中，不进行任何移动时快乐值最大，为 $0$。