‎ سعید به تازگی وارد خانه جدید خود شده و می‌خواهد آن را تزیین کند. او در نگاه اول متوجه می‌شود که دیوار این خانه دارای تعدادی سوراخ است که باید تا حد ممکن پوشیده شوند. سعید دوست دارد دو تابلو بر روی این دیوار قرار دهد که تعدادی از این سوراخ‌ها را پوشش دهند. بدون هیچ دلیلی شکل هر دو تابلو باید مربع باشد و باز بدون هیچ دلیلی این دو تابلو باید حداقل ‎$k$‎ سوراخ از این دیوار را بپوشانند‎!‎

واضح است که سعید دوست‌ دارد هنگامیکه تابلو‌ها بر روی دیوار نصب می‌شوند ضلع پایینی آن‌ها موازی زمین باشد و هم‌چنین بدیهی است که دو تابلو نمی‌توانند هم‌پوشانی داشته باشند (یعنی باید مساحت اشتراک دو تابلو صفر باشد (تابلو‌‎ها می‌توانند رو ی مرز اشتراک داشته باشند). باز هم بدون هیچ دلیلی سعید می‌خواهد اندازه دو تابلو با هم برابر باشد‎!‎

هدف سعید این است که کمینه اندازه تابلوهایی را پیدا کند که با قرار دادن آن‌ها بتواند ‎$k$‎ تا از سوراخ های دیوار را بپوشاند. دقت کنید که این نقطه‌ها می‌توانند رو مرز تابلوها هم قرار بگیرند. شما باید با گرفتن مختصات سوراخ های دیوار کمترین ‎$\alpha$‎ای را پیدا کنید که بتوان دو تابلوی مربعی موازی محور مختصات با ضلع ‎$\alpha$‎ بر روی دیوار قرار داد که حداقل ‎$k$‎ تا از سوراخ‌های دیوار زیر آن‌ها قرار بگیرند. می‌توانید سوراخ‌ها را به صورت نقطه در نظر بگیرید. ‎

• در سطر اول ورودی دو عدد ‎$n$‎ و ‎$k$‎ نشان دهنده تعداد سوراخ‌ها و حداقل تعداد سوراخ‌هایی که قرار است پوشیده شوند آمده است.
• در ‎$n$‎ سطر بعدی در هر سطر به ترتیب دو عدد صحیح ‎$x_i$‎ و ‎$y_i$‎ آمده‌اند که مختصات یک سوراخ را نشان می‌دهند.
• ‎ $1 \leq n \leq 50000$‎.
• ‎ $3 \leq k \leq n$‎.
• در ورودی هیچ دو نقطه‌ای روی هم نیستند.
• ‎ $-2\times10^5 \leq x_i,y_i \leq 2\times10^5$‎.

در تنها سطر خروجی کمترین مقدار ‎$\alpha$‎ را برای هر تست چاپ کنید.

• زیرمسئله‌ی اول (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 500$‎.
• زیرمسئله‌ی دوم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 2500$‎.
• زیرمسئله‌ی سوم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 25000$‎.
• زیرمسئله‌ی چهارم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 50000$‎.

• محدودیت زمان: ۱۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در تست نمونه کافیست دو مربع به اندازه ‎۱‎ به رئوس چهار نقطه اول ورودی و چهار نقطه دوم ورودی قرار دهیم. بدیهی است که با مربع‌های کوچک‌تر نمی‌توان این کار را انجام داد.

• سوال بعد
• سوال قبل