مربّاها و قفسه‌بندی


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

حالا که مربّاها در شیشه قرار گرفته‌اند، قرار شده که آن‌ها را در قفسه قرار دهند که مرتب باشند، چون مربّاها نظم و ترتیب را خیلی دوست دارند. مربّاها از طرفداران پر و پا قرص مد هم هستند؛ برای همین از یک طراح داخلی خواسته‌اند که یک قفسه‌بندی برای آن‌ها درست کند.

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

طرحی که به مربّاها ارائه شده از nn خط تشکیل شده. مربّاها خط iiام قفسه‌بندی را با دو مقدار aia_i و bib_i نشان می‌دهند که aia_i نشان دهنده شیب خط و bib_i نشان‌دهنده‌ی عرض از مبدا خط iiام روی جدول مختصات فرضی مربّاها است.

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

ورودی🔗

در خط اول ورودی، nn که نشان دهنده تعداد خطوط است، می‌آید. پس از آن در خط i+1i+1 ام ورودی، به ترتیب دو عدد aia_i و bib_i می‌آیند که به ترتیب نشان دهنده شیب و عرض از مبدا خط ii ام می باشند. 1n1 0001 \leq n \leq 1\ 000 109ai,bi109-10^9 \leq a_i, b_i \leq 10^9

خروجی🔗

در تنها خط خروجی تعداد قفسه‌های قفسه‌بندی پیشنهاد شده را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4
0 0
0 1
2 -1
-2 6
Plain text

خروجی نمونه ۱🔗

10
Plain text

قفسه‌بندی پیشنهاد شده به شکل زیر می‌باشد.