Module: स्कैनलाइन विधि

Problem

टॉम सॉयर ने अपने दोस्तों को आंटी पोली के घर के आसपास की बाड़ को रंगने के कठिन कार्य में मदद करने के लिए राजी किया। फेंस में k लगातार बोर्ड होते हैं, जिनकी संख्या 1 से k तक होती है, और k-वें बोर्ड के बाद फिर से पहला बोर्ड आता है।

टॉम के दोस्त बहुत दुस्साहसी हैं, I-वें दोस्त पेंटिंग में भाग लेने के लिए तभी सहमत होते हैं जब उन्हें बिल्कुल लगातार बोर्डों के एक हिस्से को पेंट करने की अनुमति दी जाती है। टॉम के पास केवल एक ब्रश है, इसलिए उसके दोस्त बारी-बारी से पेंट करेंगे और एक ही बार में पूरा खंड उन्हें आवंटित कर दिया जाएगा। टॉम के लिए केवल एक ही चीज़ बची है कि वह अपने दोस्तों को किस क्रम में आमंत्रित करना है, साथ ही प्रत्येक के लिए लगातार बोर्डों की वांछित संख्या का चयन करना है।

उसी समय, टॉम का प्रत्येक मित्र एक अप्रकाशित बाड़ बोर्ड और एक बोर्ड दोनों को चित्रित करने के लिए तैयार है जो पहले से ही उसके पूर्ववर्तियों में से एक द्वारा चित्रित किया गया है। हालाँकि, दोस्तों को एक अनपेक्षित बोर्ड को पेंट करने में अधिक आनंद मिलता है। टॉम एक नंबर x चुनना चाहता है और बाड़ के हिस्सों को पेंट करने के लिए इस तरह से वितरित करना चाहता है कि उसका प्रत्येक दोस्त कम से कम x पेंट न किए गए तख्तों को पेंट करे। टॉम अपने दोस्तों से बहुत प्यार करता है और चाहता है कि उनमें से प्रत्येक बाड़ को पेंट करने का अधिक से अधिक लाभ उठाएं, इसलिए वह x को अधिकतम करने की कोशिश करता है।

टॉम को यह समझने में मदद करें कि वह अपने दोस्तों को कितनी खुशी दे सकता है।

इनपुट डेटा प्रारूप
इनपुट फ़ाइल की पहली पंक्ति में दो पूर्णांक n (1 ≤ n ≤ 10⁵ ) और k (1 ≤ k ≤ 10⁹ ) हैं। अगली पंक्ति में n पूर्णांक हैं — मान a_i (1 ≤ a_i ≤ k).

आउटपुट डेटा स्वरूप
एक नंबर प्रिंट करें — x का अधिकतम संभव मान।
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स"> <शरीर> इनपुट आउटपुट 2 100
5 10 5 4 10
7 8 3 5 2
व्याख्या
पहले उदाहरण में x = 5 क्योंकि दोस्तों में से एक सिर्फ पाँच से अधिक बोर्ड पेंट नहीं करना चाहता। वह पहले आएगा, अपने पांच को पेंट करेगा, जिसके बाद अन्य 10 अनपेक्षित बोर्ड टॉम के दूसरे दोस्त के पास जाएंगे। बाकी के 85 बोर्ड टॉम को खुद पेंट करने होंगे।
दूसरे उदाहरण में, x = 2 तक पहुँचा जा सकता है, उदाहरण के लिए, इस तरह। सबसे पहले, तीसरा दोस्त 4 से 6 (3 बिना रंगे हुए बोर्ड) बोर्ड को पेंट करता है। फिर चौथा मित्र 1 से 5 तक के बोर्डों पर पेंट करता है (3 बिना पेंट किए हुए बोर्ड)। फिर दूसरा मित्र 1 से 8 तक के बोर्डों को पेंट करता है (2 बिना पेंट किए हुए बोर्ड)। अंत में, पहला दोस्त 6 से 10 और 1 से 2 (2 बिना पेंट वाले बोर्ड, ध्यान दें कि बाड़ एक चक्र में जाता है और ये बोर्ड एक लगातार खंड बनाते हैं) को पेंट करते हैं।