کتابخانه
در سال 2385 و در کشور «ناریا»٬ بچههای مستعد از سنین پایین وارد مدرسهای خاص میشوند تا تواناییهایشان هرچه بیشتر شکوفا گردد. در این مدرسه که «مهد المپیاد» نام دارد٬ کودکانی یافت میشوند که بیش از آنچه تصورش را کنید٬ باهوش و اهل مطالعه هستند.
تعدادی کتاب در کتابخانهی این مدرسه وجود دارد و این کودکان هر از گاهی به آنجا سر میزنند. آنها موجوداتی فوق منطقی هستند و تنها با عدد و رقم کار خود را پیش میبرند. در هر مراجعه به کتابخانه٬ یک کودک بایستی کتابی را که مدنظر دارد٬ به کتابدار معرفی کند تا وی کتاب را برایش بیاورد. کودک شمارهی بعضی صفحات کتاب درخواستی را به همراه تعداد واژههای حاضر در هر یک از صفحات به کتابدار میدهد و کتابدار بیچاره است که بایستی همهی کتابها را جستجو کرده و کتابی را که با شرایط کودک همخوانی دارد٬ برایش بیاورد!
در یک فرایند «حالگیری»٬ کتابدار ادعا کرده که تنها درصورتی کتاب را تحویل میدهد که مشخصات ارائه شده دقیقا یک کتاب را مشخص کند. کودکان المپیادی هم که سرشان درد میکند براین اینجور حالگیریها!
برنامهای بنویسید که بادریافت اطلاعات همهی کتابها و مشخص بودن کتاب درخواستی٬ کوتاهترین دنبالهای را بیابد که کودک را به آن کتاب برساند. برای راحتی کار شما٬ فرض کردهایم که تعداد صفحات کتابها یکسان است.
ورودی
- در سطر نخنست ورودی٬ دو عدد صحیح $n$ و $m$ آمدهاند که به ترتیب نشاندهندهی تعداد کتابها و تعداد صفحات هر کتاب است.
- در هر یک از $n$ سطر دیگر٬ $m$ عدد صحیح آمده که نشاندهندهی تعداد واژههای هر صفحهی یک کتاب است؛ به صورت دقیقتر $j$امین عدد واقع در سطر $i+1$ام تعداد واژههای $j$امین صفحه از کتاب $i$ام را نشان میدهد.
- اولین کتاب ورودی کتاب مورد درخواست کودک میباشد.
- $1 \leq n \leq 100$
- $1 \leq m \leq 13$
- تعداد واژههای هر صفحهی یک کتاب عددی صحیح و نامنفی است که از $1000$ تجاوز نمیکند.
خروجی
- در صورتی که چنین دنبالهای (که کتاب درخواستی یکتا تعیین کند) وجود نداشت٬ در خروجی٬ تنها عبارت No Solution را چاپ کنید.
- در غیر این صورت٬ در نخستین سطر خروجی٬ یک عدد صحیح بنویسید که نشاندهندهی کمینهی تعداد صفحاتی است که باید مشخص کنیم تا کتاب مزبور به صورت یکتا معلوم گردد.
- در سطر دیگر شماره صفحات مربوطه را به ترتیب صعودی بنویسید. در صورتی که مسئله چند جواب داشت٬ جوابی را در خروجی بنویسید که ترتیب الفبایی آن از سایر جوابهای بهینه کمتر باشد.
محدودیتها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 5 10 20 10 10 10 10 10 15 10 10 15 20 10 10 10 | 2 1 2 |
توضیحات
واضح است که در صورتی که کودک تنها صفحات یک و دو رانشان کند؛ هیچ کتابی بهجز کتاب اول (که مد نظر اوست) صفحهی اولش دارای $10$ واژه وصفحهی سومش نیز دارای $10$ واژه نیست. درضمن روشن است که با یک صفحه٬ کتاب اول یکتا تعیین نمیشود. البته صفحات یک و سه نیز میتوانند یک جواب بهینه باشند و لی ترتیب الفبایی یک و دو مقدم بر آن است.