题目描述

译自 NOISG 2023 Final T3. Airplane

兔子本森想要驾驶飞机！

有 $n$ 个区域供本森飞行，编号从 $1$ 到 $n$。每个区域 $i$ 因地形限制有最低飞行高度 $a[i]$，本森在该区域飞行时必须达到此高度。

此外，由于盛行风条件和本森缺乏飞行经验（毕竟他是一只兔子），他只能在特定区域对之间飞行。有 $m$ 个这样的区域对，编号从 $1$ 到 $m$，第 $j$ 个区域对 $u[j]$ 和 $v[j]$ 表示本森可以在区域 $u[j]$ 和 $v[j]$ 之间双向飞行。使用这些允许的区域对，总是可以从任一区域到达所有其他区域。

初始时，本森在区域 $1$，高度为 $0$。他希望前往区域 $n$，并在着陆时高度必须为 $0$。

每分钟，本森可以选择留在当前区域或前往另一区域。在同一分钟内，他的高度可以增加 $1$，减少 $1$ 或保持不变。然而，当本森到达一个区域时，他的高度必须至少达到该区域要求的最低高度。本森在区域 $n$ 着陆所需的最短时间是多少？

输入格式

程序需从标准输入读取数据。

输入的第一行包含两个空格分隔的整数 $n$ 和 $m$，分别表示区域数量和本森可在区域间飞行的区域对数量。

下一行包含 $n$ 个空格分隔的整数 $a[1], a[2], \ldots, a[n]$，表示每个区域的最低飞行高度。

接下来的 $m$ 行，每行包含两个空格分隔的整数，第 $j$ 行包含 $u[j]$ 和 $v[j]$，表示本森可以在区域 $u[j]$ 和 $v[j]$ 之间双向飞行。

输出格式

程序需向标准输出输出结果。

输出一个整数，表示本森在区域 $n$ 着陆所需的最短时间。

3 2
0 2 0
1 2
2 3

4

本森从区域 $1$ 前往区域 $3$，可在 $4$ 分钟内完成：

• 第 $1$ 分钟，本森留在区域 $1$，高度从 $0$ 增加到 $1$。
• 第 $2$ 分钟，本森从区域 $1$ 飞到区域 $2$，高度从 $1$ 增加到 $2$。
• 第 $3$ 分钟，本森从区域 $2$ 飞到区域 $3$，高度从 $2$ 减少到 $1$。
• 第 $4$ 分钟，本森留在区域 $3$，高度从 $1$ 减少到 $0$。

这个样例满足所有子任务的限制。

11 12
0 0 0 0 0 0 2 2 1 5 0
1 2
2 3
3 4
4 5
5 6
6 11
1 7
7 8
8 9
9 11
1 10
10 11

5

本森从区域 $1$ 前往区域 $11$，可在 $5$ 分钟内完成：

• 第 $1$ 分钟，本森留在区域 $1$，高度从 $0$ 增加到 $1$。
• 第 $2$ 分钟，本森从区域 $1$ 飞到区域 $7$，高度从 $1$ 增加到 $2$。
• 第 $3$ 分钟，本森从区域 $7$ 飞到区域 $8$，高度保持为 $2$。
• 第 $4$ 分钟，本森从区域 $8$ 飞到区域 $9$，高度从 $2$ 减少到 $1$。
• 第 $5$ 分钟，本森从区域 $9$ 飞到区域 $11$，高度从 $1$ 减少到 $0$。

这个样例满足子任务 $2,3,4$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 200000$
• $1 \leq m \leq 400000$
• $0 \leq a[i] \leq 10^{8}$
• $a[1]=a[n]=0$
• $1 \leq u[j], v[j] \leq n, u[j] \neq v[j]$

详细子任务附加限制及分值如下表所示：