سُرّت أبقار Farmer John حين علمت أن السنة الصينية الجديدة قد احتُفل بها مؤخرًا، إيذانًا ببدء عام الثور الذي تحبه الأبقار دائمًا.
كما نعلم، تتكرر حيوانات التقويم الصيني في دورة من اثني عشر عامًا: الثور والنمر والأرنب والتنين والأفعى والحصان والماعز والقرد والديك والكلب والخنزير والفأر، ثم الثور مجددًا. والأقل شهرة أن بوابة زمنية غامضة تُفتح في كل عام للثور، فتتيح للأبقار السفر إلى أي عام آخر للثور في الماضي أو المستقبل.
تريد البقرة Bessie الاستفادة من البوابة التي فُتحت هذا العام لزيارة $N$ من أسلافها المشهورين من الأبقار الذين عاشوا منذ زمن بعيد، حيث $1 \leq N \leq 0x10000$ (يبدو من الملائم في عام الثور كتابة الحد الأعلى لـ$N$ بالنظام الست عشري؛ لاحظ أن 0x10000 يساوي 65536).
للأسف، يُشعر السفر عبر الزمن Bessie ببعض الغثيان، وتفضل ألا تقوم بأكثر من $K$ قفزات زمنية ($1 \leq K \leq N$). ساعدها على تحديد أقل عدد من السنوات اللازمة لزيارة جميع أسلافها والعودة إلى العام الحالي، مع القيام بما لا يزيد على $K$ قفزات زمنية إجمالًا خلال الرحلة.
لا يلزم Bessie استخدام البوابة في عام معين للثور إذا لم ترغب في ذلك. تربط البوابات الأيام الأولى من أعوام الثور بعضها ببعض. مثلًا، إذا وصلت Bessie إلى بوابة ثم انتظرت اثني عشر عامًا حتى البوابة التالية، فإنها تقضي اثني عشر عامًا بالضبط في هذه العملية. تبدأ المغامرة في اليوم الأول من عام الثور الحالي، لذا يمكنها العودة إلى الماضي فورًا. لا يعيش أي من أسلاف Bessie في أعوام الثور.
الإدخال
يحتوي السطر الأول على $N$ و$K$. تحتوي الأسطر $N$ التالية على $N$ أعداد صحيحة مختلفة في النطاق $1 \ldots 10^9$، تحدد منذ كم سنة عاش كل واحد من أسلاف Bessie البالغ عددهم $N$.
الإخراج
اطبع أقل عدد من السنوات اللازمة لكي تزور Bessie جميع أسلافها وتعود إلى العام الحالي.
أمثلة
الإدخال 1
5 3 101 85 100 46 95
الإخراج 1
36
ملاحظة
إحدى طرق زيارة جميع الأسلاف والعودة خلال ست وثلاثين سنة هي الآتية:
- الدخول إلى البوابة في الوقت الحاضر والسفر إلى ما قبل ثمان وأربعين سنة.
- الانتظار اثنتي عشرة سنة، ثم دخول البوابة قبل ست وثلاثين سنة من الحاضر والسفر إلى ما قبل مئة وثماني سنوات.
- الانتظار أربعًا وعشرين سنة، ثم دخول البوابة قبل أربع وثمانين سنة من الحاضر والعودة إلى العام الحالي.
واضعا المسألة: Brian Dean و David Yang