جک بعد از دستبرد معروفش از غول قصه، تصمیم گرفت با غارت بقیه‌ی غول‌ها پول بیش‌تری به‌دست آورد. برای همین $n$ لوبیای سحرآمیز را با فاصله‌های معینی از خانه‌ی خودش، پشت سر هم و بر روی یک خط کاشت و هفت روز و هفت شب از آن‌ها مراقبت کرد تا رشد کنند و بلند شوند…

حال زمان برداشت محصول رسیده و جک می‌خواهد اموال غول‌ها را تصاحب کند؛ اما یک مشکل کوچک وجود دارد: جک بعد از تصاحب اموال همه‌ی غول‌ها باید از تنه‌ی اولین درخت لوبیا (یعنی درخت با کم‌ترین فاصله تا خانه‌اش) پایین بیاید و به سرعت همه‌ی درخت‌ها را «بیندازد». البته برای انجام این مهم، تنها کاری که می‌تواند انجام دهد قطع کردن تعدادی از درخت‌ها با تبر است. جک به دلیل تمرین‌هایی که در زمان فقر خود داشته، می‌تواند یک درخت را طوری «قطع» کند که به انتخاب او به سمت چپ یا راست «بیفتد». خانه‌ی جک در سمت چپ همه‌ی لوبیاها قرار دارد. البته «افتادن» یک درخت لوبیا بر روی یک درخت دیگر، باعث می‌شود که آن درخت نیز به همان سمت «بیفتد». به عبارت دقیق‌تر فرض کنید فاصله‌ی درختی که «می‌افتد» تا خانه‌ $D$ باشد و ارتفاع آن نیز $H$ باشد؛ اگر درخت به راست بیفتد، هر درخت سالم‌ای (هنوز نیفتاده) که در فاصله‌ی $D$ تا $D+H$ از خانه باشد ($D\leq x \leq D+H$) به سمت راست می‌افتد و اگر درخت به چپ بیفتد،‌هر درخت سالمی که در فاصله‌ی $D-H$‌تا $D$ از خانه باشد ($D-H\leq x \leq D$) به سمت چپ می‌افتد.

حال جک می‌خواهد قبل از عملیات بداند، که با قطع کردن حداقل چندتا از درخت‌ها (و تعیین این که هر درخت قطع شده به کدام سمت بیفتد) می‌تواند کاری کند که همه‌ی درخت‌ها بیفتند. البته برای سادگی می‌توانید فرض کنید جک درخت‌هایی را که می‌خواهد قطع کند، به ترتیب از چپ به راست(از نزدیک‌ترین به دورترین) قطع می‌کند. یعنی جک بعد از پایین آمدن از سمت چپ‌ترین درخت، در طول حرکاتش برای قطع کردن درخت‌ها، هیچ‌گاه به سمت چپ حرکت نمی‌کند و همواره یکی از درخت‌های باقی‌مانده در سمت راست خود را قطع می‌کند. به طور مثال در ورودی نمونه، اگر بخواهد در انتها درخت‌های ۱ و ۶ و ۴ را با تبر قطع کند، باید ابتدا ۱ را قطع کند، سپس ۴ و در آخر ۶ را قطع کند.( هم‌چنین پر واضح است که یک درخت افتاده را نمی‌توان قطع کرد!)

برنامه‌ای بنویسید که:

• فاصله و ارتفاع درخت‌های لوبیاهای سحرآمیز را از ورودی بخواند.
• کم‌ترین تعداد درخت‌هایی را که می‌توان با قطع آن‌ها همه‌ی درخت‌ها را انداخت محاسبه کند.
• این تعداد کمینه را در خروجی بنویسید.

• در سطر اول ورودی، عدد $n$ قرار دارد.($1\leq n\leq 10^6$ و هیچ‌کدام از اعداد ورودی از $10^8$ بیش‌تر نمی‌شود)
• در هر یک از $n$ سطر بعد، دو عدد صحیح نامنفی با فاصله از هم آمده‌اند. در خط $i$ ام از این $n$ سطر، عدد اول نمایش‌دهنده‌ی فاصله درخت لوبیای $i$ام تا خانه و عدد دوم نشان‌دهنده‌ی ارتفاع آن درخت است. توجه کنید که فاصله‌‌ی لوبیاها در ترتیب ورودی اکیدا صعودی هستند(لوبیای $i$ام سمت چپ لوبیای $i+1$ام قرار دارد).

در تنها سطر خروجی کم‌ترین تعداد درخت‌هایی را بنویسید که با قطع آن‌ها می‌توان همه‌ی درخت‌ها را انداخت.

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

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