某日本岛上有 $N$ 座城市和 $M$ 条单向道路连接这些城市。每座城市都有一座博物馆，博物馆在偶数天开放，在奇数天关闭。第 $i$ 座城市的博物馆内藏有 $w_i$ 件北斋艺术品。

Bytika 在一个偶数天的早晨抵达了岛上的主城（位于城市 $0$）。每天，她都会参观当前所在城市的博物馆（如果该博物馆当天开放且她之前未曾参观过），并于当晚通过当前城市出发的任意一条道路移动到另一座城市（可能是她已经访问过的城市）。如果 Bytika 无法离开当前城市，或者没有机会看到新的北斋艺术品，她就会乘飞机离开该岛。

求 Bytika 能看到的最多的北斋艺术品数量。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$, $0 \le m \le \min(n \cdot (n - 1), 10^5)$)，分别表示城市数量和道路数量。第二行包含 $n$ 个整数 $w_0, w_1, \dots, w_{n-1}$，其中第 $i$ 个整数表示第 $i$ 座城市博物馆中北斋艺术品的数量 ($0 \le w_i \le 1000$)。接下来的 $m$ 行，每行包含两个整数 $s_j$ 和 $t_j$，表示有一条从城市 $s_j$ 到城市 $t_j$ 的单向道路 ($0 \le s_j, t_j \le n - 1$, $s_j \neq t_j$, 若 $i \neq j$ 则 $(s_j, t_j) \neq (s_i, t_i)$)。

输出格式

输出一个整数：Bytika 在岛上旅行期间能看到的不同北斋艺术品的最大数量。

样例

样例输入 1

2 1
1 2
0 1

样例输出 1

1

样例输入 2

5 5
1 1 1 1 1
0 1
1 2
2 3
3 0
3 4

样例输出 2

3

样例输入 3

4 4
1 1 1 1
0 1
1 2
2 0
2 3

样例输出 3

4