‎مِـمُـل یک شخصیت کوچولو و محبوب کارتونی است (‎ شاید شما یادتون نیاد!). یک‌روز صبح، ‎مِـمُـل می‌خواست به خانه‌ی دخترمهربان(‎ شخصیت محبوبِ ‎مِـمُـل)‎ برود؛ اما در میانه‌ی راه متوجه شد که بارانِ شبِ گذشته، رودخانه‌ای به عرض ‎$d$‎ واحد را در مسیر همیشگی‌اش به‌وجود آورده است. برای راحتی کار، رودخانه را یک بازه‌ی باز روی محور ‎$x$‎ها ‎(افقی)‎ بگیرید که از نقطه صفر (جایی که مِـمُـل‎‎ هست) تا نقطه‌ی ‎$d$‎ روی محور را پوشانده است.

خوش‌بختانه در این رودخانه ‎$n$‎ عدد سنگِ ریز و محکم در فاصله‌های ‎$s_1$‎ تا ‎$s_n$‎ از لبه‌ی رودخانه (نقطه‌های ‎$s_1$‎ تا ‎$s_n$‎ محور ‎$x$ها)‎ قرار دارند. هم‌چنین ‎$m$‎ قورباغه‌ی چاق نیز در نقاط ‎$f_1$‎ تا ‎$f_m$‎ قرار گرفته‌اند.

پس از کمی جست‌وجو، برای عبور از این رودخانه، مِـمُـل‎ یک تکه چوب دراز به‌طول ‎$k$‎ پیدا کرد. می‌دانیم با استفاده از این چوب و سنگ‌هایی که درون رودخانه وجود دارند، اگر مِـمُـل‎ در نقطه‌ی ‎$x$‎ باشد و یک سنگ در فاصله‌ی ‎$t$‎ از آن نقطه قرار داشته باشد و ‎$t \le k$‎، آن‌وقت مِـمُـل‎ می‌تواند چوب‌اش را دراز کرده و روی سنگ بگذارد و با حرکتی شبیه قهرمان‌های پرش با نیزه (‎ولی به‌جای از صفر تا ‎۹۰‎ درجه، از صفر تا ‎۱۸۰‎ درجه‎!‎) به نقطه‌ای با فاصله‌ی ‎$2t$‎ از ‎$x$‎، در راستای سنگ برود. یعنی اگر سنگ جلوی (سمت راست) ‎$x$‎ بود (نقطه‌ی ‎$x+t$‎) در آن‌صورت مِـمُـل می‌تواند به نقطه‌ی ‎$x+2t$‎ برود و اگر سنگ سمت چپ ‎$x$‎ بود (نقطه‌ی ‎$x-t$‎) در آن‌صورت ‎مِـمُـل به‌خانه‌ی ‎$x-2t$‎ می‌رود.

توجه کنید که چون سنگ‌ها به‌شدت لغزنده هستند، مِـمُـل فقط می‌تواند روی قورباغه‌ها و زمین بایستد‎!‎ هم‌چنین چون چوب خیلی سنگین است، مِـمُـل‎ نمی‌تواند روی زمین (از نقطه‌ی صفر به سمت چپ) راه برود، اما می‌تواند با چند پرش رفت و برگشت در نقطه‌ای عقب‌تر از نقطه‌ی اوّلیه‌اش (مثلاً ‎$-2$‎) قرار بگیرد. و نیز می‌دانیم فقط سنگ‌ها (و نه زمین) می‌توانند به عنوان تکیه‌گاه ‎(مرکز)‎ پرش قرار بگیرند‎) ‎چون نوک چوب تیز است، در زمین نرم و نیز بدن قورباغه‌ها ‎(اوووچ!)‎ فرو می‌رود!).

هدف نهایی مِـمُـل نیز قرار گرفتن در نقاط ‎$d$‎ یا جلوتر از آن (بیش‌تر از ‎$d$‎) است که در آن‌صورت چوب را رها کرده و به‌سمت خانه‌ی دختر مهربان می‌دود. اما از آن‌جا که هر پرش (با چوب، به‌مثابه نیزه‎!‎) برای ‎مِـمُـل‎، یک دقیقه طول می‌کشد، مِـمُـل‎ می‌خواهد در کم‌ترین زمان ممکن از رودخانه عبور کند. به ‎مِـمُـل کمک کنید و برنامه‌ای بنویسید که با خواندن ‎$d$‎، تعداد و محل سنگ‌ها و قورباغه‌ها و نهایتاً طول چوبش ‎($k$)‎ مشخّص کند که ‎مِـمُـل حداقل پس از چند دقیقه به آن‌طرف رودخانه می‌رسد.

• در سطر اوّل ورودی، به‌ترتیب از چپ به راست چهار عدد ‎$d$ (عرض رودخانه)، سپس ‎$n$ (تعداد سنگ‌ها)، بعد ‎$m$ (تعداد قورباغه‌ها) و نهایتاً ‎$k$ (طول چوب ‎مِـمُـل)‎ آمده است.
• در سطر دوم ورودی ‎$n$‎ عدد (نه لزوماً مرتّب) آمده است که هر کدام محل یکی از سنگ‌ها را نشان می‌دهد.
• در سطر سوم ورودی ‎$m$‎ عدد (نه لزوماً مرتّب) آمده است که هر کدام محل یکی از قورباغه‌ها را نشان می‌دهد.
• تمام اعداد ورودی صحیح و مثبت‌اند.
• تمام سنگ‌ها و قورباغه‌ها در نقاط صحیح داخل رودخانه (بازه‌ی ‎$[1‎, ‎d-1]$‎) قرار دارند.
• هیچ دو سنگ، دو قورباغه یا یک سنگ و یک قورباغه‌ای در یک مکان قرار ندارند.
• $1\le n \le 2~000$‎.
• ‎ $1\le m \le 5\times10^4$‎.
• ‎ $1\le k \le 5\times10^4$‎.
• همواره ‎$1 \le d \le 2\times10^9$‎ و در ‎۵۰‎ درصد تست‌ها، ‎$1\le d\le 2\times10^6$‎.

در صورتی که ‎مِـمُـل می‌تواند بالاخره از رودخانه عبور کند، در یک سطر کم‌ترین تعداد پرش لازم را بنویسید. در غیر این‌صورت اگر هرگز ‎مِـمُـل نمی‌تواند به نقطه‌ی ‎$d$‎ یا نقاط جلوتر از آن برسد، در تنها سطر خروجی عبارت No Solution (دقیقاً با ‎N‎ و ‎S‎‎ بزرگ) را بنویسید.

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

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