San

Έχετε ονειρευτεί ποτέ ότι ήσασταν ο κύριος χαρακτήρας σε ένα παιχνίδι υπολογιστή; Ο πρωταγωνιστής αυτής της ιστορίας, ο Branimir, έχει αυτό το όνειρο αυτή τη στιγμή.

Ο κόσμος στο όνειρο του Branimir αποτελείται από ${\rm N}$ ουρανοξύστες διατεταγμένους από αριστερά προς τα δεξιά. Για τον $i$-οστό ουρανοξύστη, γνωρίζουμε το ύψος $H_i$ και τον αριθμό των χρυσών νομισμάτων $G_i$ στην οροφή του. Το παιχνίδι ξεκινά με ένα άλμα σε οποιονδήποτε από τους ουρανοξύστες και αποτελείται από πολλά βήματα. Σε κάθε βήμα, ο Branimir μπορεί να πηδήξει σε έναν ουρανοξύστη δεξιά από αυτόν στον οποίο βρίσκεται αυτή τη στιγμή (είναι δυνατό να πηδήξει και πάνω από μερικούς από αυτούς) και αν δεν είναι χαμηλότερος από τον τρέχοντα (ουρανοξύστη). Σε κάθε στέγη ουρανοξύστη που βρίσκεται, ο Branimir θα μαζεύει όλα τα χρυσά νομίσματα. Ο Branimir μπορεί να τερματίσει το παιχνίδι μετά από οποιονδήποτε αριθμό βημάτων (και μηδέν), αλλά πρέπει να συγκεντρώσει τουλάχιστον $K$ χρυσά νομίσματα για να προχωρήσει στο επόμενο επίπεδο.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει θετικούς ακέραιους αριθμούς $N(1\le N\le 40)$ και $K(1\le K\le 4\cdot {10}^{10})$, τους αριθμούς​ από την περιγραφή εργασίας.
Η $i$-οστή από τις ακόλουθες $N$ γραμμές περιέχει δύο θετικούς ακέραιους, $H_i$ και $G_i(1\le H_i,G_i\le {10}^9)$, τους αριθμούς​ από​ την περιγραφή εργασίας.

Έξοδος

Πρέπει να τυπώσετε τον αριθμό των διαφορετικών τρόπων για να παίξετε.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας το 40% των συνολικών πόντων, θα ισχύει $N\le 20$.

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

input

4 6
2 1
6 3
7 2
5 6

output

3

Επεξήγηση του 1ου παραδείγματος:

Τα ακόλουθα τρία παιχνίδια θα μεταφέρουν τον Branimir στο επόμενο επίπεδο (οι αριθμοί αντιπροσωπεύουν τις ετικέτες των ουρανοξυστών που επισκέφτηκε): $\{1,2,3\},\{1,4\}$ και $\{4\}$.

input

2 7
4 6
3 5

output

0

input

4 15
5 5
5 12
6 10
2 1

output

4