‎$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$‎ام بالا و پایین می‌رود.‎

در تنها سطر خروجی پاسخ سوال را بنویسید.‎

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

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