Migrated from Lutece 2386 软件工程

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Kanade 再次根据自身经历写了个 Galgame 脚本，然而她还是不会编程，于是依旧交给 Yuzuru 制作。

Yuzuru 仍然是个萌新，不能完成这么大规模的 Galgame 制作，而且 HeRaNO 咕了他两次，他再也不想找这个事妈了。他突然想到了自己的名字，于是他将这个 Galgame 交给 ZuyuHard 制作。

我们都知道，开发一款游戏有很多步骤，比如角色设计，建模，场景设计，写代码，调试与测试等等。总得说来，一共有 $n$ 步，一些步骤是一开始就可以着手进行的，一些步骤需要完成了某些步骤后才能开始做，比如一开始就可以同时进行角色设计和场景设计，然后才能建模，最后才能落实到写代码上，写完代码才能调试与测试。在这个 Galgame 的开发中，这样的依赖关系共 $m$ 个。但是不会出现死锁，即不会出现 $s_1,s_2,\ldots s_p,s_1\ (p\ge 2)$ 中从第二步开始后一个步骤依赖前一个的情况。每个步骤完成需要一定的时间，第 $i$ 步完成需要的时间为 $a_i$。

大型软件的开发都是并行的，在这里我们认为 ZuyuHard 有足够的员工，并且能够同时做的步骤都会同时进行。

Yuzuru 想知道这个 Galgame 最早多长时间写完，并且还想知道每步可以摸鱼的时间之和。

定义一步的摸鱼时间为在最快完工的情况下，允许最晚开始做这步的时刻与最早开始做这步的时刻之差。

允许最晚开始做这步的时刻为在不影响结束时间的情况下，开始做这步的最大时刻。时间从第 $0$ 单位时刻开始计时。

Input

第一行两个非负整数 $n,m$ ($1\le n\le 5\times 10^5,0\le m\le 10^6$)，表示游戏开发的步骤和依赖关系数。

第二行 $n$ 个正整数 $a_i$ ($1\le a_i\le 10^9$)，表示每一步的完成时间。

接下来 $m$ 行，每行两个正整数 $u,v$ ($1\le u,v\le n,u\neq v$)，表示只有先进行 $u$ 步骤才能进行 $v$ 步骤。保证没有重复的依赖关系。

Output

输出两行，每行各一个整数。第一行输出这个 Galgame 最早多长时间写完，第二行输出每步可以摸鱼的时间之和。

Samples

4 2
3 5 2 1
1 3
2 3

7
8

8 9
11 17 16 20 14 12 13 15
1 3
2 4
4 3
3 6
5 6
2 5
6 8
5 7
7 8

80
68

Note

对于第一个样例，最初并行第 $1,2,4$ 步，$5$ 单位时间后做第 $3$ 步，$2$ 单位时间后完成。最小完成用时为 $7$。

在这种情况下，做第 $2,3$ 步都不能摸鱼，做第 $1$ 步最晚可以在第 $2$ 单位时刻开始，可以摸 $2-0=2$ 单位时间鱼，做第 $4$ 步最晚可以在第 $6$ 单位时刻开始，可以摸 $6-0=6$ 单位时间鱼，因此总摸鱼时间为 $2+6=8$。

Resources

2020 UESTC ICPC Training for Graph