Trung và FireGhost đã bị phù thủy xấu xa Lihwy nhốt vào mê cung!

Mê cung là một đồ thị gồm ~n~ phòng, các phòng được nối với nhau bởi các mật đạo; biết giữa hai căn phòng chỉ có tối đa một mật đạo, và không tồn tại mật đạo nối một căn phòng với chính nó. Hiện tại, Trung và FireGhost đang ở phòng ~1~, và để thoát ra ngoài, họ cần phải đi đến phòng ~n~. Tuy nhiên, mỗi căn phòng đều có một con quái vật đáng sợ đang chờ họ sẵn, biết con quái vật trong phòng thứ ~i~ có sức mạnh ~a_i~.

Giữa lúc đang đau khổ, thần đèn Alànhddin xuất hiện và ban cho Trung và FireGhost một thanh kiếm với sức mạnh tuỳ ý để đánh bại đám quái vật! Nếu 2 người chọn thanh kiếm có sức mạnh ~x~, họ có thể đánh bại toàn bộ quái vật có sức mạnh không vượt quá ~x~; ngược lại, họ sẽ bị con quái vật đó nuốt chửng.

Tuy nhiên, Alànhddin là một kẻ tư bản: nếu Trung và FireGhost sử dụng thanh kiếm có sức mạnh là ~x~ và số quái vật mà Trung và FireGhost cần phải tiêu diệt ít nhất để đến căn phòng ~n~ là ~y~, họ sẽ phải trả cho Alànhddin số tiền là ~|x - y|~. Hãy giúp Trung và FireGhost chọn thanh kiếm có sức mạnh phù hợp để số tiền phải trả là ít nhất có thể nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~m~ (~1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5~) — lần lượt là số phòng và số mật đạo trong mê cung.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) — sức mạnh của con quái vật trong căn phòng thứ ~i~.

~m~ dòng tiếp theo, dòng thứ ~j~ gồm ~2~ số nguyên dương ~u_j, v_j~ (~1 \le u_j, v_j \le n~) thể hiện một mật đạo nối ~2~ căn phòng ~u_j~ và ~v_j~.

Output

Một số nguyên duy nhất là đáp án của bài toán: số tiền ít nhất mà Trung và FireGhost phải trả. Nếu Trung và FireGhost không thể đến được căn phòng ~n~, in ra đáp án ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

1

Sample Input 2

2 0
1 2

Sample Output 2

-1

Notes

Trong test ví dụ thứ nhất, khi đi từ ~1~ đến ~4~, bạn phải lần lượt đánh bại ~3~ con quái vật có sức mạnh ~1~, ~4~, ~2~. Nếu thanh kiếm có sức mạnh là ~4~, Trung và FireGhost sẽ có thể đến được căn phòng ~4~ với chi phí là ~|4-3| = 1~. Vậy đáp án là ~1~.