Problem
تام سایر دوستانش را متقاعد کرد تا در کار دشوار نقاشی حصار خانه عمه پولی به او کمک کنند. حصار از k تخته متوالی تشکیل شده است که از 1 تا k شماره گذاری شده اند و بعد از k-امین تخته دوباره اولین می آید.
دوستان تام بسیار سخت گیر هستند، دوست iام فقط در صورتی موافقت می کند که در نقاشی شرکت کند که اجازه داشته باشد بخشی از تخته های متوالی را دقیقاً نقاشی کند. تام فقط یک قلم مو دارد، بنابراین دوستانش به نوبه خود و یکباره تمام بخش اختصاص داده شده به آنها را نقاشی می کنند. تنها کاری که تام باید انجام دهد این است که ترتیب دعوت دوستانش را انتخاب کند و همچنین تعداد تابلوهای متوالی مورد نظر را برای هر کدام انتخاب کند.
در همان زمان، هر یک از دوستان تام آماده است که هم یک تخته حصار رنگ نشده و هم تخته ای را که قبلاً توسط یکی از پیشینیانش نقاشی شده است، نقاشی کند. با این حال، دوستان از نقاشی یک تخته بدون رنگ لذت بیشتری می برند. تام می‌خواهد عدد x را انتخاب کند و قسمت‌های حصار را طوری تقسیم کند که هر یک از دوستانش حداقل x تخته‌های رنگ‌نشده را نقاشی کنند. تام دوستانش را بسیار دوست دارد و می‌خواهد هر کدام از آنها از نقاشی حصار نهایت استفاده را ببرند، بنابراین سعی می‌کند x را به حداکثر برساند.
به تام کمک کنید بفهمد چقدر می تواند برای دوستانش شادی بیاورد.
قالب داده های ورودی
خط اول فایل ورودی شامل دو عدد صحیح n (1 ≤ n ≤ 10
5 ) و k (1 ≤ k ≤ 10
9 ) است. خط بعدی شامل n عدد صحیح — مقادیر a
i (1 ≤ a
i ≤ k).
قالب داده خروجی
چاپ یک عدد — حداکثر مقدار ممکن
x.
<بدن>
| ورودی |
خروجی |
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 تخته رنگ نشده، توجه داشته باشید که حصار در یک چرخه می رود و این تخته ها یک بخش متوالی را تشکیل می دهند).