친구 늘리기 프로젝트

Background
경곽 34기 땅꼬마 윤기는 낯가림이 심해서 친하지 않은 사람들과 이야기하는 것을 두려워한다. 그래서 지금 윤기 주변의 친구들은 모두 윤기에게 먼저 다가와준 친구들이다. 교현이는 윤기와 친해지고 싶어서 윤기에게 다가가야 한다.

윤기와 교현이가 있는 공간은 정점이 n개인 단방향 그래프로 일반화 할 수 있다.

교현이는 1번 정점에 있고 윤기는 n번 정점에 있다. 각 정점에는 윤기가 좋아하는 음식들이 있고 교현이는 이것들을 최대한 많이 주워서 윤기에게 전해주고 싶다. 음식은 한 번만 주워갈 수 있고 정점과 간선은 여러 번 방문해도 된다.

윤기와 교현이가 만나면 더 이상 교현이는 움직일 수 없고 최대한 많은 음식을 가져온 경우에만 윤기와 교현이가 친해질 수 있다.

윤기와 교현이가 친해질 수 있게 교현이가 가져와야하는 음식의 개수를 알려주자.

input
첫 번째 줄에 정점의 개수 n(2 <= n <= 10,000)와 간선의 개수 m(1 <= m <= 100,000)이 주어진다.
두 번째 줄에는 각 정점에 있는 음식의 개수가 공백을 사이에 두고 주어진다. 각 정점의 음식의 개수는 0 부터 100개까지 이다.
다음 m개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. A번 정점과 B번 정점이 연결되어 있다는 의미이다. 방향은 A->B

output
첫 번째 줄에 교현이가 윤기에게 가져가야 할 음식의 개수를 출력. 만약 윤기에게 가는 경로가 없으면 -1을 출력.

IO Example

입력
7 9
2 5 13 4 6 8 1
1 4
4 5
5 1
1 6
6 7
2 7
7 3
3 7
7 2

출력
21