У країні $n$ міст, деякі з яких з'єднані між собою дорогами. Для того, щоб проїхати по одній дорозі потрібно один бак бензину. У кожному місті бак бензину має різну віртість. Вам потрібно дістатись з першого міста у $n$-те, витративши якомога меншу кількість грошей. \InputFile Спочатку йде кількість міст $n~(1 \le n \le 100)$, потім йде $n$ чисел, $i$-те з яких задає вартість бензину в $i$-ому місті (всі числа цілі з діапазону від $0$ до $100$). Потім йде кількість доріг $m$ в країні, далі йде опис самих доріг. Кожна дорога задається двома числами --- номерами міст, які вона з'єднує. Всі дороги двосторонні (тобто по ним можна їздити як в одну, так і в іншу сторону); між двома містами завжди існує не більше однієї дороги; не існує доріг, які ведуть з міста в себе. \OutputFile Виведіть одно число --- сумарну вартість маршруту або $-1$, якщо дістатись неможливо. \includegraphics{https://static.e-olymp.com/content/34/341ba1cdbde7f2947335938bd85415067f5437f2.gif}