शेषफल का खेल

आइए एक खेल खेलते हैं। आपके पास एक प्रारंभिक संख्या $s_0$ है और दो अनुक्रम $a_1, a_2, ..., a_n$ तथा $b_1, b_2, ..., b_n$ दिए गए हैं। आपका लक्ष्य है कि $s_0$ से 0 तक यथाशीघ्र पहुँचा जाए। प्रत्येक चरण में, आप कोई एक सूचकांक i चुन सकते हैं और वर्तमान संख्या पर निम्नलिखित ऑपरेशन लगा सकते हैं:

इस तरह आपको अगली संख्या प्राप्त होगी। आपका कार्य यह पता लगाना है कि $s_0$ से 0 तक पहुँचने में न्यूनतम कितने चरणों की आवश्यकता होगी।

इनपुट

इनपुट की पहली पंक्ति में तीन पूर्णांक n, m, और $s_0$ होंगे (0 ≤ n ≤ 10, 0 ≤ m ≤ 100000, और 0 < $s_0$ < m)।

अगली n पंक्तियों में प्रत्येक में दो पूर्णांक $a_i$ और $b_i$ दिए जाएँगे (0 ≤ $a_i$, $b_i$ ≤ $10^9$)।

आउटपुट

कार्यक्रम को 0 तक पहुँचने के लिए आवश्यक न्यूनतम चरणों की संख्या प्रदर्शित करनी चाहिए। यदि 0 तक पहुँचना संभव नहीं है, तो Impossible प्रदर्शित करना होगा।

Examples