المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۲:سوال ۱۸

آسیاب‌های المپیادی

دیروز که ما بچه‌هارو از سایت بیرون کردیم یه مشکل کوچیک برا شایان کوچولو پیش اومد. اون که طبق معمول سه، چهارتا خیابون اصلی و فرعی رو اشتباه رفته بود سرشو که بلند کرد دید که تو آسیاب المپیادی‌هاست و سعید هم جلوش واستاده. شایان کوچولو که روحش از وجود این اسیاب هم بی‌خبر بود و از دیدن یه آدم جدید ذوق کرده بود سریع گفت: «کی ول؟» سعید هم که خیلی وقت بودالمپیادی اون دور و بر ندیده بود ذوق کرد و گفت: «ای ول» و شایان کوچولو رو شوت کرد. شایان هم که هم از جواب سعید خوشش اومده بود و هم تا حالا چیزیش نشده بود یه راست وسط سنگای اصلی آسیاب فرود اومد. اینجا بود که آسیاب المپیادی‌ها هم شروع به کار کرد و شایان کوچولو شروع به آسیاب شدن کرد (همچنین آمده است «شروع به آسیاب کردن شد»). در اینجا بود که یاران حلقه جمع شدند تا شایان کوچولو رو از له شدن نجات بدن ولی چون نتونستن ما این مسئله رو به شما دادیم.

در آسیاب المپیادی‌ها ۲ گروه چرخ وجود داره: چرخ‌های بالایی که پاد ساعت‌گرد می‌چرخند و یک قطاع آهن‌ربایی دارند و چرخ‌های پایینی که ساعت‌گرد می‌چرخند و یک قطاع آهنی دارند. ما باید هر یک از چرخ‌های بالایی رو بیاریم و بر فراز یک چرخ پایینی قرار بدیم. هر چرخ با سرعت زاویه‌ای ثابت می‌چرخه و اگر در یک ثانیه صحیح، قطاع‌های آهنی و آهن‌ربایی دو چرخی که ما روی هم قرار دادیم، دقیقا روی هم قرار بگیرن، طی یک فرایند پیچیده که شرح آن در این مقال نمی‌گنجد، هر دو چرخ برای همیشه از کار می‌افتن (با این چرخ‌ها نمی‌توان چرخ دیگری را ثابت کرد). ما می‌خواهیم بدونیم که با این تفاسیر، سریع‌ترین زمانی که این چرخ‌ها رو میشه از کار انداخت و شایان کوچولو رو نجات داد کی است.

هر چرخ به $k$ قطعه تقسیم شده و هر چرخ یک سرعت زاویه‌ای مخصوص $\omega$ دارد که نشان می‌دهد، این چرخ خاص در هر ثانیه $\omega$ قسمت می‌چرخد. در ضمن می‌دانیم که در ثانیه‌ی صفر هر چرخ در چه وضعیتی قرار دارد. می‌دانیم قسمت چندم در مبدا قرار دارد.

توجه

توجه کنید که چون امتحان امروز درصد داره شایان کوچولو حتما نجات پیدا می‌کنه.

$1\leq n \leq 200$ و $1\leq k \leq 10^9$ و $0\leq w_i <k$ (سرعت زاویه‌ای‌ها) و $0\leq \theta_i< k$ .

ورودی

در سطر اول فایل ورودی $n$ (تعداد چرخ‌های پایینی، بالطبع همان تعداد چرخ‌های بالایی) و $k$ آمده‌اند.

در $n$ سطر بعدی اطلاعات مربوط به چرخ‌های بالایی و در $n$ سطر بعد اطلاعات مربوط به چرخ‌های پایینی آمده است.

در هر سطر، دو عدد $a$ و $b$ آمده است که $a$ می‌گوید قسمت چندم در ثانیه‌ی صفر در مبدا قرار دارد و $b$ سرعت زاویه‌ای این چرخ است.

خروجی

در فایل خروجی یک عدد بنویسید که کم‌ترین زمان لازم برای نجات دادن شایان کوچولو است.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 10
5 1
1 2
7 3
0 4
0 4
0 3
2 2
1 1
1

ابزار صفحه