प्रत्येक शहर में, आप टैंक को भर सकते हैं, टैंक और कनस्तर को भर सकते हैं, या कनस्तर से पेट्रोल को टैंक में डाल सकते हैं। इससे आप उन शहरों में पेट्रोल खरीदकर पैसे बचा सकते हैं जहां यह सस्ता है, लेकिन कनस्तर केवल एक टैंक भरने के लिए पर्याप्त है!
पहली पंक्ति में संख्या N (1<=N<=100) है, अगली पंक्ति में N संख्याएं हैं, i-th जिनमें से i-वें शहर में गैसोलीन की लागत निर्धारित करती है (ये सभी पूर्णांक हैं) 0 से 100 तक की सीमा)। फिर नंबर आता है M – देश में सड़कों की संख्या, उसके बाद स्वयं सड़कों का विवरण। प्रत्येक सड़क को दो संख्याओं द्वारा दिया जाता है - यह कनेक्ट होने वाले शहरों की संख्या। सभी सड़कें दो-तरफ़ा हैं (अर्थात, उन्हें एक दिशा और दूसरी दिशा दोनों में चलाया जा सकता है), दो शहरों के बीच हमेशा एक से अधिक सड़कें नहीं होती हैं, शहर से खुद की ओर जाने वाली सड़कें नहीं होती हैं।
आउटपुट
एक संख्या को आउटपुट करने के लिए आवश्यक है – मार्ग की कुल लागत, या -1 अगर वहाँ जाना असंभव है।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
4
1 10 2 15
4
1 2
1 3
4 2
4 3
2 |