در یک قفس دایره شکل به شعاع ‎$R$‎، ‎$n$‎ خرس خوابیده‌اند. رئیس باغ‌وحش قصد دارد یک سری دیوار در این قفس بسازد تا خرس‌ها به دسته‌های حداکثر ‎$k$‎ تایی دسته بندی شوند. زیرا اگر در هنگام بیدار شدن آن‌ها، بیش از ‎$k$‎ تا خرس در یک اتاق باشند، با هم دعوا می کنند. دورتادور قفس دقیقاً ‎$360$‎ تا میله با فواصل مساوی چیده شده است . میله‌ی صفرم روی نقطه‌ی ‎$(R,0)$‎ و مرکز قفس هم در ‎$(0,0)$‎ می‌باشد. شماره‌ی میله‌ها از ‎$0$‎ تا ‎$359$‎ است و درجهت پادساعت گرد افزایش می یابد. به عبارت دیگر میله‌ی ‎$i$‎ام در امتداد ‎$i$‎ درجه از مرکز (نسبت به میله ی صفرم) قرار دارد. تمام دیوارها باید بین دو میله به صورت خطی مستقیم کشیده شوند و تضمین شده که نمی‌توان دیواری کشید که از روی یک خرس عبور کند (هیچ خرسی روی خط واصل بین دو میله قرار ندارد). از طرفی دیوارها نباید در هیچ نقطه‌ای به جز در نقاط انتهایی اشتراک داشته باشند و نباید یک‌دیگر را قطع کنند. رئیس باغ‌وحش یک شرط دیگر هم می‌گذارد و آن این است که هیچ یک از اتاق‌های پدید آمده، بیش از سه گوشه نداشته باشد (چه خرسی در آن اتاق باشد و چه نباشد). برای نمونه به شکل‌های زیر توجه کنید:

در شکل‌های فوق نمونه‌هایی از دیوارکشی‌های مختلف نشان داده شده است و تعداد گوشه‌های هر ناحیه، درون آن نوشته شده است. توجه داشته باشید که فقط شکل سمت راست یک دیوارکشی معتبر است، زیرا دو شکل دیگر دارای اتاق‌هایی هستند که بیش از سه گوشه دارند.

هزینه‌ی ساخت هر دیوار ‎$l+C$‎ است که ‎$l$‎ طول دیوار و ‎$C$‎ یک عدد ثابت است . رئیس باغ‌وحش می‌خواهد این دیوارکشی علاوه بر شرط‌های گفته شده کم‌ترین هزینه‌ی ممکن را داشته باشد و برای این کار از شما کمک خواسته است (عجب رئیس پررویی!). ضمناً رئیس باغ‌وحش تضمین کرده که چنین دیوارکشی‌ای وجود دارد.

• در سطر اول ورودی، ‎۴‎ عدد صحیح ‎$N$‎ و ‎$K$‎ و ‎$R$‎ و ‎$C$‎، به ترتیب قرار دارد.
• در هر یک از ‎$N$‎ سطر بعد، دو عدد حقیقی ‎$x$‎ و ‎$y$‎ به ترتیب آمده‌اند که با فاصله از هم جدا شده اند (هر سطر مختصات یک خرس است).‎
• ‎$1 \leq K \leq N \leq 10,000$‎.
• ‎$1 \leq R \leq 10,000$‎.
• ‎$0 \leq C \leq 1,000,000$‎.
• مختصات‌ها با حداکثر سه رقم اعشار در ورودی داده می‌شوند.
• خرس‌ها همه درون قفس قرار دارند.

• در سطر اول، تعداد دیوارهایی که باید کشیده شوند را بنویسید‎.‎
• در هر یک از سطرهای بعدی، دو عدد متمایز بنویسبد که شماره‌های میله‌های دو سر یکی از دیوارهاست.

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

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