由于Acb0y的rp很低，导致每次都被mm拒之门外，因此今天他想先涨涨rp再行动。于是他挑了n家店，例如理发店、美容店、礼品店等，编号为1-n，每当他经过一家店的时候就能增加一定的rp值，且每家店最多只能经过一次。此外他还挑选了m条可供行走的路线(单向的)。起始时Acb0y在校门口(编号为0)，他的目的地是ACM实验室(编号为n+1)，你能帮我们的老队长算一下他今天rp最大可以涨到多少么(起始rp为0)？
图

Input

  每个输入文件的第一行有两个整数n和m(0< n<= 30,0< m<= 100)，第二行里有n个整数di(1 <= i<= n)表示经过店i可以涨di点的rp值(0<= di<= 100)。再接下来有m行，每行有两个整数a b表示从a可以走到b(0<=a,b<=n+1)。

Output

  对于每个输入文件，输出Acb0y能够涨到的最大rp值。

Sample Input


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


Sample Output


5

Hint

两点之间可能有多条边，且中可能存在环。

不行啊，当测试数据变为
4 6
5 2 2 2
0 1
0 2
1 4
1 3
2 3
3 4
结果就会变成0啊

我中间节点没有变啊，我只是增加了一条从三到四的路，这样最大就会变成5+2等于七了啊

呵呵。。。你是对的，但是我昨天提交了一下，显示是超时的，可能递归比较耗时，你能再给个优化的代码吗

呵呵。。。你是对的，但是我昨天提交了一下，显示是超时的，可能递归比较耗时，你能再给个优化的代码吗

你都猜对了，那你是哪个学校的？你至少也有大三了吧？

恩，可以啊，你要那两道测试数据我发给你啊

恩，我明天找管理员要，明天发给你吧