====== Elevators ====== ‎$n$‎ آسانسور متفاوت به شما داده شده است ، شما باید یکی از این آسانسورها را انتخاب کنید و دقیقاً ‎$m$‎ بار از آن استفاده کنید. ‎ در هر استفاده از آسانسور ‎$i$‎ام شما یا می‌توانید ‎$d_i$‎ طبقه پایین بیایید (اگر شماره طبقه شما حداقل ‎$d_i$‎ باشد) یا این که ‎$u_i$‎ طبقه بالا بروید. شما باید آسانسور را طوری انتخاب کنید و طوری از آن استفاده کنید که بعد از ‎$m$‎ بار استفاده در پایین‌ترین طبقه‌ی ‎$x \geq 1$‎ قرار داشته باشید. ‎ با فرض این که شما کار خود را در طبقه همکف ( شماره ‎$0$) شروع می‌کنید و ساختمانی که در آن قرار دارید بی‌نهایت طبقه دارد، مقدار ‎$x$‎ را در خروجی چاپ نمایید. ===== وروید ===== * در سطر اول ورودی دو عدد ‎$1 \leq m \leq 1000000$‎ و ‎$1 \leq n \leq 2000$‎ آمده است. * در ‎$n$‎ سطر بعد یک جفت عدد ‎$1 \leq u_i \leq 1000$‎ و ‎$1 \leq d_i \leq 1000$‎ آمده‌اند که نشانگر تعداد طبقه‌هایی هستند که آسانسور ‎$i$‎ام بالا و پایین می‌رود.‎ ===== خروجی ===== در تنها سطر خروجی پاسخ سوال را بنویسید.‎ ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |10 3‎ \\ 15 12‎ \\ 15 4‎ \\ 7 12 | 13 | * [[سوال ۱۴|سوال بعد]] * [[سوال ۱۲|سوال قبل]]