شاه ترناس به وزیرش دستور داده که یک بازی فکری برای پسرش آرتوس طراحی کند تا قابلیت‌های فکری پسرش بالا برود. وزیر یک بازی فکری به این صورت طراحی کرد. ‌$N$ صندوق با شماره‌های $۱$ تا $N$ قرار داده شده است. هر صندوق یک قفل مخصوص دارد که تنها با استفاده از کلید مخصوص آن باز می‌شود. قبل از شروع بازی وزیر به ازای هر $i$ دو کپی از کلید صندوق $i$ را داخل صندوق‌های $i - 1$ و $i + 1$ (در صورت وجود) قرار داد. سپس $D$ الماس در $D$ صندوق متفاوت قرار داد. در آخر، همه صندوق‌ها را قفل کرد و کلید $M$ صندوق را به او داد. آرتوس باید تمام الماس‌ها را جمع‌آوری کند طوری که تعداد صندوق هایی که در طی جمع‌آوری الماس‌ها باز کرده کمینه شود.

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

• ورودی از چند سناریو مختلف تشکیل شده است. در خط اول هر سناریو عدد‌های $N (1 \leq N \leq 500)$ تعداد صندوق‌ها،‌ $M (1 \leq M \leq N)$ تعداد کلید‌های داده شده به آرتوس و $D (0 \leq D \leq N)$ تعداد الماس‌ها آمده است.
• در خط بعدی $M$ عدد آمده که نشان‌دهنده صندوق‌هایی است که کلید آن‌ها به آرتوس داده شده است. شماره صندوق‌هایی که الماس در آن‌ها وجود دارد نیز در خط بعدی آمده است.
• ورودی با خطی شامل سه عدد $0$ تمام می‌شود.

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

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

• سوال بعد