该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面描述：

有 $n$ 个区域，喵喵可以在这些区域飞行，这些区域编号为 $1$ 到 $n$。对于每个区域 $i$，由于地形限制，喵喵在该区域内飞行的最低高度为 $a[i]$。

此外，由于风力条件和喵喵缺乏飞行经验（毕竟他是一只猫咪），他只能在某些成对的区域之间飞行。共有 $m$ 对这样的区域对，编号为 1 到 $m$，第 $j$ 对 $u[j]$ 和 $v[j]$ 表示喵喵可以在区域 $u[j]$ 和 $v[j]$ 之间双向飞行。通过这些区域对，这 $n$ 个区域可以互相到达。

最初，喵喵位于区域 $1$，高度为 $0$。他想要前往区域 $n$，并且着陆时必须以高度 $0$ 结束。

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

输入：

第一行输入两个正整数 $n, m$

第二行输入 $n$ 个整数 $a_i$

接下来 $m$ 行每行输入一对 $u_j, v_j$

• $1 \le n \le 2 \times 10^5$
• $1 \le m \le 4 \times 10^5$
• $0 \le a_i \le 10^8$
• $a_1=a_n=0$

输出：

输出一个整数代表最少花费时间

样例输入1:

3 2
0 2 0
1 2
2 3

样例输出1：

4

样例输入2:

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

样例输出2：

5

提示：

样例1解释: 喵喵正在从区域 1 前往区域 3。他可以在 4 分钟内完成。

• 第 1 分钟，喵喵停留在区域 1。他将高度从 0 增加到 1。
• 第 2 分钟，喵喵从区域 1 前往区域 2。他将高度从 1 增加到 2。
• 第 3 分钟，喵喵从区域 2 前往区域 3。他将高度从 2 降低到 1。
• 第 4 分钟，喵喵停留在区域 3。他将高度从 1 降低到 0。

样例2解释: 喵喵正在从区域 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。