დროის ლიმიტი: 2 წმ
მეხსიერების ლიმიტი: 256 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, IX-X
სანდრო ჯერ მხოლოდ მე-6 კლასის მოსწავლეა, მაგრამ უკვე ინფორმატიკის საოლიმპიადო ჯგუფში მეცადინეობს და შარშან ქვეყნის მასშტაბით ჩატარებულ ოლიმპიადაშიც პირველად მიიღო მონაწილეობა, სადაც თავისზე გაცილებით უფროს მოსწავლეებს ეპაექრებოდა და ერთი ამოცანის სრულად ამოხსნაც მოახერხა. ეს მისთვის პირველი დიდი წარმატება გახლდათ და, ამიტომ, გადაწყვიტა ამ ამბის აღსანიშნავად მეგობრებთან ერთად მოელხინა.
მან თავისი მეგობრები კვირა დღეს, საღამოს ექვსი საათისთვის მოიწვია და მეგრული ხაჭაპურის დიდი რაოდენობაც შეუკვეთა. თუმცა, მოხდა არასასიამოვნო ფაქტი - ხაჭაპურები დაგეგმილზე გაცილებით ადრე მოიტანეს. რადგანაც სტუმრების მოსვლის დროისათვის ხაჭაპურები უკვე გარანტირებულად გაცივებული იქნება, წინასწარ მოსაფიქრებელია მათი გაცხელების პროცესის ორგანიზაცია. სანდრო მხოლოდ დამწყები პროგრამისტია და ამ ამოცანის გადაჭრისათვის საჭირო თეორიული ცოდნა ჯერ არა აქვს. მან დახმარებისათვის თქვენ მოგმართათ, თუმცა, წინასწარ მოახდინა ამოცანის მკაცრი ფორმულირება:
- ai აღნიშნავს i-ური ხაჭაპურის გასაცხელებლად საჭირო დროს წამებში;
- bi აღნიშნავს იმ დროს წამებში, რომლის განმავლობაშიც ხაჭაპური ცხელი რჩება.
შესატანი მონაცემები: სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ერთი მთელი დადებითი N რიცხვი (1≤N≤300 000) – ხაჭაპურების რაოდენობა. მომდევნო N რაოდენობის სტრიქონი შეიცავს ხაჭაპურების აღწერას. თითოეულ მათგანში ჩაწერილია ერთი ჰარით გამოყოფილი ორი ai და bi რიცხვი (1≤ai,bi≤109).
გამოსატანი მონაცემები: სტანდარტული გამოტანის ერთადერთ სტრიქონში გამოიტანეთ ერთი მთელი რიცხვი - იმ ხაჭაპურების მაქსიმალური რაოდენობა, რომლებიც შეიძლება ერთდროულად იყოს ცხელი.
შეფასება:
ტესტების 20%-ში N≤10;
ტესტების 20%-ში N≤20;
ტესტების 20%-ში N≤5 000.
შესატანი მონაცემები
2 1 1 1 1 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება
შესატანი მონაცემები
4 2 12 10 8 7 5 5 1 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება
გავარჩიოთ დაწვრილებით პირველი ტესტი:
· დროის 2 მომენტში გამოიღებს ღუმელიდან მეორე ხაჭაპურს. დროის ამ მომენტში პირველი ხაჭაპური ჯერ კიდევ ცხელია. შესაბამისად, ამოცანის პასუხია 2. ყურადღება მიაქციეთ იმას, რომ ორი ხაჭაპური ცხელი იქნება დროის მხოლოდ ამ მომენტში და იმის მიღწევა, რომ ისინი ცხელი იყოს დროის რაიმე არანულოვანი სიგრძის შუალედში, ამ მაგალითში შეუძლებელია.