Planine

Ο Zoran περιπλανιέται στην πατρίδα του, τη Δαλματία, για να ξεχάσει τα ερωτικά του προβλήματα. Συνάντησε ένα βουνό συγκεκριμένου σχήματος, πίσω από το οποίο τον περιμένει μια νεαρή κοπέλα. Το βουνό μπορεί να περιγραφεί με n εναλλασσόμενα χαμηλά και ψηλά σημεία, όπου το n είναι περιττό. Τα σημεία με μονούς δείκτες, εκτός από το πρώτο και το τελευταίο σημείο, ονομάζονται κοιλάδες.

Ο Zoran φοβάται το σκοτάδι. Ακόμη και το κάλεσμα της αγάπης δεν θα του δώσει κουράγιο να διασχίσει το βουνό τη νύχτα. Ως συνήθως, οι νεράιδες του Velebit έρχονται στη διάσωση.

Μοντελοποιούμε κάθε νεράιδα με μια φωτεινή κουκκίδα σε σταθερό ύψος h. Μια νεράιδα φωτίζει την κοιλάδα εάν και μόνο εάν το τμήμα που συνδέει τη νεράιδα και την κοιλάδα δεν τέμνει το εσωτερικό του βουνού.

Ποιος είναι ο ελάχιστος αριθμός νεράιδων που μπορεί να φωτίσουν όλες τις κοιλάδες ταυτόχρονα;

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~n~ (~3 \le n < 10^6~, n περιττός) και ~h\;(1 \le h \le 10^6)~, τον αριθμό των σημείων που περιγράφουν το βουνό και το ύψος στο οποίο ζουν οι νεράιδες.

Η ~i~-οστή από τις ακόλουθες n γραμμές περιέχει ακέραιους αριθμούς ~x_i~ και ~y_i\;(-10^6 \le x_i \le 10^6, 0 \le y_i < h)~, τις συντεταγμένες του ~i~-οστού σημείου του βουνού.

Είναι σίγουρο ότι ~x_1 < x_2 <\;\ldots\;< x_n~ και ~y_1 < y_2,\;y_2 > y_3,\;y_3 < y_4,\;\ldots,\;y_{n-1} > y_n~

Έξοδος

Μία γραμμή με τον ελάχιστο αριθμό νεράιδων, έτσι ώστε όλες οι κοιλάδες να φωτίζονται.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~y_2\;=\;y_4\;=\;\ldots\;=\;y_{n-1}~
2	30	~3 \le n < 2000~
3	60	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

9 6
0 0
1 2
3 0
6 3
8 1
9 2
11 1
12 4
14 0

output

1

input

9 5
-5 2
-4 3
-2 1
0 4
2 2
3 3
4 1
5 2
6 1

output

2

Εξήγηση των παραδειγμάτων:

Το πρώτο παράδειγμα φαίνεται στην εξήγηση του προβλήματος.

Μπορεί να φανεί ότι οι κοιλάδες στο δεύτερο παράδειγμα δεν μπορούν να φωτιστούν χρησιμοποιώντας μόνο μία νεράιδα. Ένα
παράδειγμα με δύο νεράιδες δίνεται στο παρακάτω σχήμα.