ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / 9-р анги /

/ Өмнөх бодлоготой ерөнхийдөө ижил, гагцхүү машины банктай ижил хэмжээтэй 1 канистр авч яваа. /

Улс N хоттой ба тэдгээрийн нилээд нь хоорондоо замаар холбогдсон. Аль ч хоёр хотын хоорондох замд адилхан нэг банк шатахуун зарцуулдаг. Хот бүрд банк шатахууны үнэ харилцан адилгүй. 1 дүгээр хотоос гарч N дүгээр хотод очихын тулд зарцуулах шатахууны хамгийн бага үнийг ол.

Нэг хотоос нөгөө хот хүрэхэд шаардагдах машины банкинд байгаа бензиныг мөн канистрт нөөцөлж болно.

Альч хотоос машиныхаа банк болон канистрт бензин дүүргэж болохоос гадна шаардлагатай үед канистраасаа машиныхаа банк руу бензин хийж болно.

Input

Эхний мөрөнд натурал N тоо өгөгдөнө. (1<=N<=100)

Дараагийн мөрөнд 1-ээс N хүртэлх хотуудын банк шатахууны үнэ дарааллаараа өгөгдөнө. Үнэ тус бүр [0; 100] завсрын бүхэл тоо байна.

Гурав дахь мөрөнд улс дахь хот хоорондын замын тоо өгөгдөнө.

Дараагийн мөрөнд зам бүр нь холбогдсон хоёр хотынхоо дугааруудаар өгөгдөнө. Зам бүр нь хоёр урсгалтай. Хоёр хотын хооронд нэгээс олон зам байхгүй.

Output

Шатахууны нийлбэр дүн. Боломжгүй бол -1.

Example

Input:
4

1 10 2 15

4

1 2 1 3 4 2 4 3

Output:
2

Input:
4

1 10 2 15

0
Output:
-1

Нэгдүгээр жишээний оновчтой шийд нь 1-ээс 3-т, дараа нь 4-т. Шатаахуунаа 1, 3-р хотуудаас худалдан авна.