لوحة السياج
Problem
أقنع توم سوير ن من أصدقائه بمساعدته في المهمة الصعبة المتمثلة في طلاء السياج المحيط بمنزل العمة بولي. يتكون السياج من k لوحات متتالية ، مرقمة من 1 إلى k ، وبعد اللوحة k يأتي أول واحد مرة أخرى.
أصدقاء توم شديدو الحساسية ، ويوافق الصديق الأول على المشاركة في الرسم فقط إذا سُمح له برسم قسم من الألواح المتتالية بالضبط. توم لديه فرشاة واحدة فقط ، لذلك سيرسم أصدقاؤه بالتناوب وفي الحال كل المقطع المخصص لهم. الشيء الوحيد المتبقي على توم القيام به هو اختيار الترتيب الذي سيدعو به أصدقائه ، وكذلك اختيار العدد المطلوب من اللوحات المتتالية لكل منها.
في الوقت نفسه ، كل صديق من أصدقاء توم مستعد لطلاء لوح سياج غير مطلي ولوحة رسمها بالفعل أحد أسلافه. ومع ذلك ، يستمتع الأصدقاء أكثر برسم لوحة غير مصبوغة. يريد توم اختيار رقم x وتوزيع أقسام السياج ليتم رسمها بحيث يرسم كل من أصدقائه على الأقل عددًا من الألواح غير المصبوغة. يحب توم أصدقائه كثيرًا ويريد أن يحصل كل منهم على أقصى استفادة من طلاء السياج ، لذلك يحاول تعظيم x.
ساعد توم على فهم مقدار الفرح الذي يمكن أن يجلبه لأصدقائه.
إدخال تنسيق البيانات
يحتوي السطر الأول من ملف الإدخال على عددين صحيحين n (1 & le؛ n & le؛ 10 5 ) و k (1 & le؛ k & le؛ 10 9 ). السطر التالي يحتوي على عدد صحيح n & [مدش]؛ القيم a i (1 & le؛ a i & le؛ k).
تنسيق بيانات الإخراج
طباعة رقم واحد و [مدش] ؛ أقصى قيمة ممكنة لـ x .
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
2100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
شرح
في المثال الأول ، x = 5 لأن أحد الأصدقاء لا يريد رسم أكثر من خمسة ألواح. سيأتي أولاً ، ويرسم الخمسة ، وبعد ذلك ستذهب 10 ألواح أخرى غير مصبوغة إلى صديق توم الثاني. سيتعين على توم نفسه رسم اللوحات الـ 85 المتبقية.
في المثال الثاني ، يمكن الوصول إلى x = 2 ، على سبيل المثال ، على هذا النحو. أولاً ، الصديق الثالث يرسم اللوحات من 4 إلى 6 (3 ألواح غير مصبوغة). ثم يرسم الصديق الرابع الألواح من 1 إلى 5 (3 ألواح غير مصبوغة). ثم يرسم الصديق الثاني الألواح من 1 إلى 8 (لوحان غير مصبوغان). أخيرًا ، يرسم الصديق الأول الألواح من 6 إلى 10 ومن 1 إلى 2 (لوحان غير مصبوغان ، لاحظ أن السياج يمر في دورة وتشكل هذه الألواح جزءًا متتاليًا).