Gremlini

Τα Gremlins είναι μικρά, αστεία, χνουδωτά πλάσματα. Στο παρελθόν προκαλούσαν σάλο, αλλά τώρα τα περισσότερα από αυτούς ζουν αξιοπρεπείς, έντιμες οικογενειακές ζωές.

Υπάρχουν ~N~ διαφορετικοί τύποι gremlins, κωδικοποιημένοι με αριθμούς ~1~ έως ~N~ για τη διευκόλυνσή σας. Ο θρύλος λέει ότι πριν από ~T~ χρόνια συνέβη ένα εργαστηριακό ατύχημα που προκάλεσε τη γέννηση ~N~ gremlins, ενός από κάθε τύπο.

Όπως όλοι γνωρίζετε, για να αναπαραχθούν τα gremlins, δεν απαιτούνται τελετουργίες ζευγαρώματος. Απλώς προσθέστε λίγο νερό και θα πάρετε αμέσως μερικά νέα κουκούλια.

Τα gremlins τύπου ~i~ χρειάζονται ακριβώς ~Y_i~ χρόνια για να ωριμάσουν και να γεννήσουν ~K_i~ κουκούλια. Για κάθε κουκούλι γνωρίζετε πόσα χρόνια χρειάζονται για να εκκολαφθεί και ποιος τύπος gremlin περιέχεται μέσα. Το αρχικό gremlin δυστυχώς πεθαίνει ενώ παράγει κουκούλια.

Τώρα, ~T~ χρόνια μετά το αρχικό ατύχημα, οι επιστήμονες αναρωτιούνται ποια είναι η μεγαλύτερη προγονική αλυσίδα της οποίας το γονιδίωμα αντιπροσωπεύεται επί του παρόντος. Ενδιαφέρονται μόνο για τους προγόνους των εκκολαφθέντων gremlins, όχι για εκείνα που έχουν ακόμα κουκούλι. Μπορείτε να υποθέσετε με ασφάλεια ότι όλα τα gremlins που έπρεπε να εκκολαφθούν φέτος το έκαναν.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς: αριθμός τύπων gremlin ~N~ και αριθμός ετών μετά το αρχικό ατύχημα, ~T\;(1 \le N \le 100,\; 1 \le T \le 10^{15})~.

Οι επόμενες ~3\cdot N~ γραμμές περιέχουν περιγραφές για τον τύπο του gremlin, τρεις γραμμές ανά τύπο:

• Η πρώτη γραμμή περιέχει ακέραιους αριθμούς, ~K_i~: αριθμός κουκουλιών που σχηματίζονται όταν αυτός ο τύπος gremlin αναπαράγεται και ~Y_i~ ~(1 \le K_i \le 1000,\;1 \le Y_i \le 1000)~, χρόνια που αυτός ο τύπος gremlin χρειάζεται για να ωριμάσει.
  
• Η δεύτερη γραμμή περιέχει ~K_i~ ακέραιους αριθμούς μεταξύ ~1~ και ~N~ συμπεριλαμβανομένων των τύπων gremlin που εκκολάπτονται από κουκούλια που σχηματίζονται από αυτόν τον τύπο gremlin.
  
• Η τρίτη γραμμή περιέχει ~K_i~ ακέραιους μεταξύ ~1~ και ~1000~, που αντιπροσωπεύουν το χρόνο εκκόλαψης για κάθε κουκούλι, σε χρόνια.
  

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου θα πρέπει να περιέχει το μήκος της τρέχουσας μεγαλύτερης προγονικής αλυσίδας.

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

input

1 42
1 10
1
5

output

2

input

2 42
1 10
1
5
1 5
1
5

output

3

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

Το αρχικό gremlin που εκκολάφθηκε στο ατύχημα, μετά από 10 χρόνια γεννά ένα μόνο κουκούλι και πεθαίνει.

15 χρόνια μετά το ατύχημα, ένα νέο gremlin εκκολάπτεται από το κουκούλι. Η προγονική του αλυσίδα περιέχει ένα gremlin. 25 χρόνια μετά το ατύχημα αυτό το gremlin γεννά ένα νέο κουκούλι και πεθαίνει.

30 χρόνια μετά το ατύχημα, ένα νέο gremlin εκκολάπτεται από το κουκούλι. Η προγονική του αλυσίδα περιέχει δύο gremlins. 40 χρόνια μετά το ατύχημα αυτό το gremlin γεννά νέο κουκούλι και πεθαίνει.

42 χρόνια μετά το ατύχημα, το σημερινό κουκούλι δεν έχει ακόμη εκκολαφθεί, οπότε η μεγαλύτερη προγονική αλυσίδα που έχει καταγραφεί ποτέ είναι δύο gremlins σε μήκος.

input

3 8 
4 5
1 2 3 2
1 2 1 3
1 1
3
1
2 1
1 2
2 1

output

4