ქალაქის კონტური

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

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

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

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

წყარო: USACO, 2005/06, NOV, SILVER


ფერმერი ჯონის ძროხებისთვის დღის საყვარელი ნაწილი მზის ჩასვლაა. ისინი ჰორიზონტზე შორეული ქალაქის კონტურს ხედავენ. ბესის აინტერესებს რამდენი შენობაა ქალაქში. დაწერეთ პროგრამა, რომელიც ძროხებს დაეხმარება გაარკვიონ მინიმუმ რამდენი შენობაა ქალაქში, მის კონტურზე დაყრდნობით.
ქალაქის არქიტექტურა საკმაოდ ერთფეროვანია. ქალაქის კონტური სიგანეში 1-დან W ერთეულამდეა (1 <= W <= 1,000,000) და აღიწერება N (1 <= N <= 50,000) ცალი თანმიმდევრულად მოცემული x და y კოორდინატით (1 <= x <= W, 0 <= y <= 500,000), რომელიც აღწერს წერტილებს სადაც კონტურის სიმაღლე იცვლება.
კონტურის ერთ-ერთი მაგალითი:
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX


რომელიც დაშიფრული იქნება შემდეგნაირად: (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1).
ამ კონტურს სჭირდება მინიმუმ 6 შენობა შესადგენად. ქვემოთ მოცემულია შენობეების განლაგების ერთი შესაძლო შემთხვევა.
..........................   ..........................    ..........................
.....22.........333.......   .....XX.........XXX.......    .....XX.........XXX.......
.111.22.......XX333XX.....   .XXX.XX.......5555555.....    .XXX.XX.......XXXXXXX.....
X111X22XXX....XX333XXXXXXX   4444444444....5555555XXXXX    XXXXXXXXXX....666666666666

შესატანი მონაცემები:

* სტრიქონი 1: ჰარით გაყოფილი ორი მთელი რიცხვი - N და W.
* სტრიქონები 2..N+1: ჰარით გაყოფილი ორი მთელი რიცხვი, იმ წერტილის x და y კოორდინატები, სადაც კონტურის სიმაღლე იცვლება. x კოორდინატები მოცემულია მნიშვნელობათა ზრდადობით და პირველი x კოორდინატი ყოველთვის ტოლია 1-ის.

გამოსატანი მონაცემები:

* სტრიქონი 1: კონტურზე გამოსახული შენობების მინიმალური რაოდენობა.



 




მაგალითები

შესატანი მონაცემები
10 26 1 1 2 2 5 1 6 3 8 1 11 0 15 2 17 3 20 2 22 1 დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება