Es gibt N Städte im Land, von denen einige durch Straßen miteinander verbunden sind. Um die gleiche Straße zu befahren, ist ein Tank mit Benzin erforderlich. Darüber hinaus haben Sie einen Benzinkanister, der genauso viel Kraftstoff enthält wie der Benzintank.
In jeder Stadt hat ein Benzintank unterschiedliche Kosten. Sie müssen von der ersten Stadt zur N-Ten gelangen und so wenig Geld wie möglich ausgeben.
Sie können in jeder Stadt einen Tank nachfüllen, einen Tank und einen Kanister nachfüllen oder Benzin aus dem Kanister in den Tank gießen. Dies spart Geld, indem Sie Benzin in Städten kaufen, in denen es billiger ist, aber die Kanister reichen nur für eine Tankfüllung aus!
Eingabe
In der ersten Zeile wird die Zahl N eingegeben (1<=N<=100), in der nächsten Zeile gibt es N Zahlen, von denen i die Benzinkosten in der ersten Stadt angibt (dies sind ganze Zahlen im Bereich von 0 bis 100). Dann kommt die Anzahl der M – die Anzahl der Straßen im Land, gefolgt von der Beschreibung der Straßen selbst. Jede Straße wird durch zwei Zahlen angegeben; die Städte, die sie verbindet. Alle Straßen sind beidseitig (das heißt, Sie können sowohl in eine als auch in die andere Richtung fahren), es gibt immer nicht mehr als eine Straße zwischen den beiden Städten, es gibt keine Straßen, die von der Stadt zu sich selbst führen.
Ausgabe
Sie müssen eine Zahl ausgeben, die Gesamtkosten der Route oder -1, wenn Sie nicht erreicht werden können.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |