Sau khi phân tích dữ liệu từ các trạm hiện trường tại các khu vực, các tuyến đường di chuyển cần được đánh giá để hình thành hành lang cứu trợ hiệu quả. Có ~N~ khu vực cứu trợ và có ~M~ đường đi một chiều nối trực tiếp giữa các khu vực.

~N~ khu vực và ~M~ đường đi được mô hình hóa như một đồ thị có hướng gồm ~N~ đỉnh được đánh số từ ~1~ đến ~N~ và ~M~ cạnh có hướng, trong đó cạnh ~(u, v)~ biểu diễn có đường đi trực tiếp từ đỉnh ~u~ đến đỉnh ~v~. Đỉnh ~1~ là sở chỉ huy và đỉnh ~N~ được xác định là khu vực cứu trợ trọng điểm. Tại đỉnh ~i~ có ~A_i~ đơn vị nguồn lực có thể huy động cho nhiệm vụ. Hành trình của đội cứu trợ xuất phát tại đỉnh ~1~ và phải kết thúc tại đỉnh ~N~. Trên hành trình này, đội cứu trợ đi qua đỉnh nào thì được huy động nguồn lực tại đỉnh đó, có thể đi qua một đỉnh nhiều lần nhưng chỉ huy động nguồn lực tại đỉnh đó ~1~ lần.

Yêu cầu: Hãy xác định tổng nguồn lực lớn nhất có thể huy động được trên một hành trình từ đỉnh ~1~ đến đỉnh ~N~. Luôn tồn tại ít nhất một đường đi từ đỉnh ~1~ đến đỉnh ~N~.

Input

• Dòng ~1~ chứa hai số nguyên ~N, M~ ~(2 \le N \le 2 \cdot 10^5; 1 \le M \le 4 \cdot 10^5)~;

• Dòng ~2~ chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ~(1 \le A_i \le 10^9; 1 \le i \le N)~;

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ biểu diễn cho một cạnh có hướng nối trực tiếp từ đỉnh ~u~ đến đỉnh ~v~ ~(1 \le u, v \le N, u \ne v)~.

Output

Ghi ra một dòng chứa một số nguyên duy nhất là tổng nguồn lực lớn nhất có thể huy động được.

Scoring

Sample Input 1

5 6
6 5 12 3 8
1 2
1 5
2 3
2 4
3 2
3 5

Sample Output 1

31

Sample Input 2

6 7
5 4 8 3 6 10
1 2
2 3
3 2
3 4
2 5
5 4
4 6

Sample Output 2

36

Notes

Trong ví dụ thứ nhất, có thể đi ~1 \rightarrow 2 \rightarrow 3 \rightarrow 5~. Tổng nguồn lực lớn nhất có thể huy động được là ~6 + 5 + 12 + 8 = 31~.

Trong ví dụ thứ hai, có thể đi ~1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 6~. Đỉnh ~2~ được đi qua hai lần nhưng nguồn lực tại đỉnh này chỉ được tính một lần. Tổng nguồn lực lớn nhất có thể huy động được là ~5 + 4 + 8 + 6 + 3 + 10 = 36~.