D. 魔法少女素世世
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
"和我签订契约，成为魔法少女吧！"
— Incubator
"只要是我能做的，我什么都愿意做！"
— Soyorin

为了复活 CRYCHIC，素世与丘比签订契约成为了魔法少女，但代价是素世需要讨伐魔女以补充足够的魔力。

现在素世正准备去讨伐迷途的魔女，迷途的魔女藏身在一个有 $$$n$$$ 个房间的迷宫内，并且拥有 $$$n-1$$$ 个分身。其中，魔女的本体位于编号为 $$$n$$$ 的房间内，而魔女的分身分别位于编号 $$$1$$$ 到 $$$n-1$$$ 的房间。

这些房间之间由单向的通道连接，每个房间都有单向通往其它的房间的通道。其中，如果一个房间不能通过通道进入，则代表它可以直接通过迷宫入口进入，即你可以直接从这里开始讨伐。

由于迷途的魔女本身的特性，这个迷宫保证了，从每个房间出发都可以到达第 $$$n$$$ 号房间，并且通道不会在房间之间成环。

每个魔女都有相应的魔力值，第 $$$i$$$ 个房间的魔女的魔力值为 $$$a_i$$$。当素世在房间内遇到魔女时，素世会与魔女展开战斗。

假设当前素世的魔力值为 $$$x$$$：

  • 如果 $$$x\ge a_i$$$，素世可以轻松消灭魔女，并且素世的魔力值 $$$x$$$ 会增加 $$$a_i$$$

  • 否则，素世只能勉强消灭魔女，并且素世的魔力值 $$$x$$$ 会减少 $$$a_i-x$$$。

在任何时刻，如果素世的魔力值 $$$x\le 0$$$，那么素世就失败了。

因此素世想知道，要成功打败魔女本体，即消灭位于 $$$n$$$ 号房间内的魔女，至少需要有多少魔力值才能进入迷宫内？

Input

第一行两个整数 $$$n,m$$$ ($$$1\le n\le 10^5, 0\le m\le 2\cdot 10^5$$$)，分别表示迷宫的房间数量，和房间之间单向通道的数量。

第二行 $$$n$$$ 个整数，第 $$$i$$$ 个整数表示第 $$$i$$$ 个房间的魔女的魔力值 $$$a_i$$$ ($$$1\le a_i\le 10^9$$$)。

接下来 $$$m$$$ 行，每行两个整数 $$$u,v$$$ ($$$1\le u,v\le n$$$)，表示一条从 $$$u$$$ 号房间通往 $$$v$$$ 号房间的单向通道。

数据保证给定图不存在重边和自环，且是一个有向无环图。

Output

一行一个整数，表示最少所需的进入迷宫的魔力值。

Examples
Input
1 0
1
Output
1
Input
4 3
1 2 5 5
1 3
2 3
3 4
Output
2
Input
8 10
3 2 1 2 3 4 3 2
1 2
1 4
2 3
2 4
3 4
4 6
5 8
5 6
6 8
7 8
Output
3
Note

对于样例 1：

  • 唯一的房间（房间 $$$1$$$）里有魔女本体，魔力值为 $$$1$$$。
  • 素世至少需要魔力值 $$$x = 1$$$ 才能进入迷宫并击败魔女。

对于样例 2：

  • 如果从房间 $$$1$$$ 开始，需要至少 $$$x = 3$$$ 的魔力值：击败房间 $$$1$$$ 的魔女后，$$$x=3+1=4$$$。
  • 如果从房间 $$$2$$$ 开始，需要至少 $$$x = 2$$$ 的魔力值：击败房间 $$$2$$$ 的魔女后，$$$x=2+2=4$$$。
  • 然后通过房间 $$$3$$$，击败房间 $$$3$$$ 的魔女后，$$$x=4-(5-4)=3$$$。
  • 然后通过房间 $$$4$$$，击败房间 $$$4$$$ 的魔女后，$$$x=3-(5-3)=1$$$。
  • 因此素世至少需要魔力值 $$$x = 2$$$ 才能进入迷宫并击败魔女。