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

---

وحید مدیرعامل مجموعه توریستی «بی‌آبان» در کویر لوط است. مهیج‌ترین بازی این مجموعه، لیز خوردن از تپه‌های شنی است. در این مجموعه $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