• محدودیت زمان: ۱.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون نهایی دوم دوره ۲۷ المپیاد کامپیوتر

---

وحید مدیرعامل مجموعه توریستی «بی‌آبان» در کویر لوط است. مهیج‌ترین بازی این مجموعه، لیز خوردن از تپه‌های شنی است. در این مجموعه \(n\) تپه شنی وجود دارد که از \(0\) تا \(n-1\) شماره‌گذاری شده‌اند. ارتفاع تپه‌ی \(i\)، \(h_i\) است. \(m\) راه شنی تپه‌ها را به هم متصل می‌کند، راه \(i\)، تپه \(v_i\) و \(u_i\) را به یکدیگر متصل می‌کند. می‌توان از تپه \(i\) به تپه \(j\) لیز خورد، اگر بین این دو تپه راه شنی وجود داشته باشد و \(h_j \le h_i\).

وحید می‌خواهد در مجموعه‌اش بتوان از تپه \(0\) شروع کرد و با لیز خوردن به تپه \(n-1\) رسید. برای اینکار او می‌تواند ارتفاع تپه‌ها را تغییر دهد، برای تغییر ارتفاع تپه‌ای از \(x\) به \(y\) باید \(|x-y|\) هزینه کند. او حق پدری بر گردن کامپیوتری‌ها دارد، به او کمک کنید و کمترین هزینه برای اینکه او به خواسته‌اش برسد را بگویید.

ورودی

در سطر اول ورودی، دو عدد \(n\) و \(m\) آمده‌است.

در سطر دوم، \(n\) عدد \(h_0, h_1, \dots, h_{n-1}\) آمده‌است.

سپس در \(i\) امین سطر از \(m\) سطر بعدی، دو عدد \(v_i\) و \(u_i\) آمده‌است.

\[1 \le n, m \le 1\ 000\] \[0 \le h_i \le 10^9\] \[0 \le v_i, u_i < n\]

خروجی

در تنها سطر خروجی، کمترین هزینه برای رسیدن وحید به خواسته‌اش را چاپ کنید. اگر چنین کاری ممکن نبود، \(-1\) چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۸	\(n \le 5\)
۲	۲۱	گراف داده شده درخت است.
۳	۲۸	\(n \le 100\)
۴	۴۳	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3 2
30 20 10
0 1
1 2

خروجی نمونه ۱

0

ورودی نمونه ۲

2 1
10 20
0 1

خروجی نمونه ۲

10

ورودی نمونه ۳

3 1
1396 1396 1396
0 1

خروجی نمونه ۳

-1