शेषफल का खेल
आइए एक खेल खेलते हैं। आपके पास एक प्रारंभिक संख्या है और दो अनुक्रम तथा दिए गए हैं। आपका लक्ष्य है कि से 0 तक यथाशीघ्र पहुँचा जाए। प्रत्येक चरण में, आप कोई एक सूचकांक
i चुन सकते हैं और वर्तमान संख्या पर निम्नलिखित ऑपरेशन लगा सकते हैं:इस तरह आपको अगली संख्या प्राप्त होगी। आपका कार्य यह पता लगाना है कि से 0 तक पहुँचने में न्यूनतम कितने चरणों की आवश्यकता होगी।
इनपुट
इनपुट की पहली पंक्ति में तीन पूर्णांक
n, m, और होंगे (0 ≤ n ≤ 10, 0 ≤ m ≤ 100000, और 0 < < m)।अगली
n पंक्तियों में प्रत्येक में दो पूर्णांक और दिए जाएँगे (0 ≤ , ≤ )।आउटपुट
कार्यक्रम को 0 तक पहुँचने के लिए आवश्यक न्यूनतम चरणों की संख्या प्रदर्शित करनी चाहिए। यदि 0 तक पहुँचना संभव नहीं है, तो
Impossible प्रदर्शित करना होगा।Examples
Input | Output |
2 5 1
3 1
2 1 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB