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

Улс 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:
3

Input:
4

1 10 2 15

0
Output:
-1

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