У країні \(𝑁\) міст, деякі з яких з'єднані між собою дорогами. Для того, щоб проїхати однією дорогою, потрібен один бак бензину. У кожному місті бак бензину має різну вартість. Вам потрібно дістатися з першого міста в \(𝑁\)-е, витративши якнайменшу кількість грошей.

При цьому є ще каністра для бензину, куди входить стільки ж бензину, скільки входить у бак. У кожному місті можна заправити бак, залити бензин у каністру, залити і туди і туди, або перелити бензин з каністри в бак.

Вхідні дані

У вхідному потоці записано спочатку число \(𝑁\) (\(1 ≤ 𝑁 ≤100\)), потім йде \(𝑁\) чисел, \(𝑖\)-е з яких задає вартість бензину в \(𝑖\)-му місті (все це цілі числа з діапазону від 0 до 100).

Потім йде число \(𝑀\) - кількість доріг в країні, далі йде опис самих доріг. Кожна дорога визначається двома числами — номерами міст, які вона з'єднує. Всі дороги двосторонні (тобто ними можна їздити як в одну, так і в іншу сторону), між двома містами завжди існує не більше однієї дороги, не існує доріг, що ведуть з міста в себе.

Вихідні дані

У вихідний потік виведіть одне число - сумарну вартість маршруту або -1, якщо дістатися неможливо.

Приклад вхідних даних

9 2

Приклад вихідних даних

4

Приклад вхідних даних

12 3

Приклад вихідних даних

2