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

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

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