სანდრო ჯერ მხოლოდ მე-6 კლასის მოსწავლეა, მაგრამ უკვე ინფორმატიკის საოლიმპიადო ჯგუფში მეცადინეობს და შარშან ქვეყნის მასშტაბით ჩატარებულ  ოლიმპიადაშიც პირველად მიიღო მონაწილეობა, სადაც თავისზე გაცილებით უფროს მოსწავლეებს ეპაექრებოდა და ერთი ამოცანის სრულად ამოხსნაც მოახერხა. ეს მისთვის პირველი დიდი წარმატება გახლდათ და, ამიტომ, გადაწყვიტა ამ ამბის აღსანიშნავად  მეგობრებთან ერთად მოელხინა.

            მან თავისი მეგობრები კვირა დღეს, საღამოს ექვსი საათისთვის მოიწვია და მეგრული ხაჭაპურის დიდი რაოდენობაც შეუკვეთა. თუმცა, მოხდა არასასიამოვნო ფაქტი - ხაჭაპურები დაგეგმილზე გაცილებით ადრე მოიტანეს. რადგანაც სტუმრების მოსვლის დროისათვის ხაჭაპურები უკვე გარანტირებულად გაცივებული იქნება, წინასწარ მოსაფიქრებელია მათი გაცხელების პროცესის ორგანიზაცია. სანდრო მხოლოდ დამწყები პროგრამისტია და ამ ამოცანის გადაჭრისათვის საჭირო თეორიული ცოდნა ჯერ არა აქვს. მან დახმარებისათვის თქვენ მოგმართათ, თუმცა, წინასწარ მოახდინა ამოცანის მკაცრი ფორმულირება:

• სულ სანდროს N რაოდენობის ხაჭაპური აქვს;
• მისი მიზანია შეარჩიოს მიკროტალღურ ღუმელში ხაჭაპურების გაცხელების ისეთი მიმდევრობა, რომ დროის რაიმე მომენტში ცხელი იყოს რაც შეიძლება მეტი ხაჭაპური;
• ყოველი ხაჭაპური ხასიათდება ზუსტად ორი a_i და b_i პარამეტრით:

-         a_i აღნიშნავს i-ური ხაჭაპურის გასაცხელებლად საჭირო დროს წამებში;

-         b_i აღნიშნავს იმ დროს წამებში, რომლის განმავლობაშიც ხაჭაპური ცხელი რჩება.

• ხაჭაპურების გასაცხელებლად შეიძლება გამოყენებული იქნას მხოლოდ მიკროტალღური ღუმელი, რომელიც სანდროს ზუსტად ერთი ცალი აქვს. ხაჭაპური რომ გაცხელდეს, იგი უნდა იმყოფებოდეს ღუმელში ზუსტად a_i წამის ტოლი დროის უწყვეტი პერიოდის განმავლობაში;
• დროის ყოველ მომენტში ღუმელში შეიძლება იმყოფებოდეს არაუმეტეს ერთი ხაჭაპურისა;
• შეიძლება ჩაითვალოს, რომ მიკროტალღურ ღუმელთან დაკავშირებული ყველა ოპერაცია მყისიერად ხდება (ჩართვა და გამორთვა, ხაჭაპურის შედება და გამოღება), ანუ ამაზე დრო არ იხარჯება;
• შეიძლება ასევე ჩაითვალოს, რომ ხაჭაპურების შეჭმაც მყისიერად ხდება. სხვა სიტყვებით, საჭიროა იმის მიღწევა, რომ მაქსიმალური რაოდენობის ხაჭაპურები  იყოს ცხელი დროის რაიმე მომენტში, არა აუცილებლად რაიმე არანულოვანი სიგრძის შუალედში.

            შესატანი მონაცემები: სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ერთი   მთელი დადებითი N რიცხვი (1≤N≤300 000) – ხაჭაპურების რაოდენობა. მომდევნო N რაოდენობის სტრიქონი შეიცავს ხაჭაპურების აღწერას. თითოეულ მათგანში ჩაწერილია ერთი ჰარით გამოყოფილი ორი a_i და b_i რიცხვი (1≤a_i,b_i≤10⁹).

გამოსატანი მონაცემები: სტანდარტული გამოტანის ერთადერთ სტრიქონში გამოიტანეთ ერთი მთელი რიცხვი - იმ ხაჭაპურების მაქსიმალური რაოდენობა, რომლებიც შეიძლება ერთდროულად იყოს ცხელი.

შეფასება:

ტესტების 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
                  დაკოპირება

შენიშვნა

გავარჩიოთ დაწვრილებით პირველი ტესტი: 

• დროის ნულოვან მომენტში სანდრო დებს ღუმელში პირველ ხაჭაპურს;
• დროის 1 მომენტში იგი გამოიღებს ღუმელიდან პირველ ხაჭაპურს და შედებს მეორეს;

·        დროის 2 მომენტში გამოიღებს ღუმელიდან მეორე ხაჭაპურს. დროის ამ მომენტში პირველი ხაჭაპური ჯერ კიდევ ცხელია. შესაბამისად, ამოცანის პასუხია 2. ყურადღება მიაქციეთ იმას, რომ ორი ხაჭაპური ცხელი იქნება დროის მხოლოდ ამ მომენტში და იმის მიღწევა, რომ ისინი ცხელი იყოს დროის რაიმე არანულოვანი სიგრძის შუალედში, ამ მაგალითში შეუძლებელია.