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

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

برای توضیح سوال به صورت دقیق‌تر، فرض کنید $P$، مرز فعلی، یک مجموعه از پاره‌خط‌های نامتقاطع باشد که در آن شروع و پایان هر پاره‌خط دو نقطه مرزی است. فرض کنید $p_{0}, p_{1}, ..., p_{N}$ این نقاط مرزی باشند. در واقع، $P$ تشکیل شده از پاره‌خط‌هایی است که $p_{i}$ را به $p_{i + 1}$ وصل می‌کند (به ازای هر $0 \leq i < N$).

سازمان ملل پیشنهاد داد که مرز جدیدی به نام $C$ با نقاط مرزی $c_{0}, c_{1}, ..., c_{K}$ انتخاب شود به صورتی که $c_{0} = p_{0}$ و $c_{K} = p_{N}$ و همچنین شرط‌های زیر نیز در آن برقرار باشد.

1. هر نقطه مانند $c_{i}$ باید یکی از نقاط $p_{0}, p_{1}, ..., p_{N}$ باشد. بدیهی‌است، اگر $c_{i} = p_{r}$ و $c_{i + 1} = p_{s }$ آنگاه $s > r$.
2. فاصله هر نقطه مانند $p_{i}$ از $C$ باید حداکثر $D$ باشد. فاصله یک نقطه مانند $p_{i}$ از $C$ برابر است با فاصله $p_{i}$ از نزدیک‌ترین نقطه بر روی $C$. توجه کنید که پاره‌خط کشیده شده از $p_{i}$ به نزدیک‌ترین نقطه بر روی $C$ همواره بر $C$ عمود است.

شما باید مرز جدید یعنی $C$ را طوری تعیین کنید که کم‌ترین طول ممکن را (با رعایت کردن شرط‌های بالا) داشته باشد.

• ورودی از چند سناریو مختلف تشکیل شده است. در خط اول هر سناریو عدد‌های $N (2 \leq N \leq 100)$ و $D (0 \leq D \leq 500)$ به ترتیب آمده است.
• در هر یک از $N$ خط بعدی دو عدد $x_{i}, y_{i} (-10000 \leq x_{i}, y_{i} \leq 10000)$ آمده است که نشان دهنده مختصات نقطه $p_{i}$ است. توجه کنید که مختصات نقطه ها صعودی است،‌ یعنی $x_{i} < x_{i + 1}$ و $y_{i} < y_{i + 1}$.
• ورودی با خطی شامل دو عدد $0$ تمام می‌شود.

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

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

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