ასკინკილა

დროის ლიმიტი: 4 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: BULG, შუმენი, 2007, B3


ბუბამ მარცხენა ფეხი იტკინა, ამიტომ ახლა მხოლოდ ცალი ფეხით დახტის. მას სიბრტყეზე მონიშნული ჰქონდა n წერტილი მთელი კოორდინატებით, თუმცა ახლა შეუძლია ისინი მხოლოდ არაკლებადი თანმიმდევრობით გაიაროს. სხვაგვარად რომ ვთქვათ, ბუბას A (x1, y1) წერტილიდან B (x2, y2) წერტილში მისვლა მხოლოდ მაშინ შეუძლია, თუ x1≤x2 და y1≤y2. დაწერეთ პროგრამა, რომელიც გაარკვევს იმ განსხვავებული წერტილების მაქსიმალურ რაოდენობას, რომელთა გავლაც ბუბას შეუძლია.

შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი n (1≤n≤106). მომდევნო n სტრიქონიდან თითოეულში მოცემულია ორ-ორი მთელი რიცხვი - შესაბამისი წერტილის კოორდინატები. ყველა კოორდინატი არაუარყოფითი მთელი რიცხვია, არაუმეტეს 109-სი.

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

 




მაგალითები

შესატანი მონაცემები
5 3 2 5 0 0 0 6 1 5 0 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

ნახტომების თანმიმდევრობაა (0,0)-(5,0)-(6,1) .