Tree Pruning

Μας δίνεται ένα "ριζωμένο" δέντρο με ~N~ κόμβους στον οποίο κάθε κόμβος έχει το πολύ δύο παιδιά. Καθε κόμβος μπορεί να είναι μαύρος ή λευκός. Ορίζουμε ένα "κλάδεμα" ως τη διαγραφή ενός κόμβου και του υποδέντρου που έχει ρίζα εκείνο τον κόμβο από το δέντρο. Με δεδομένο έναν ακέραιο αριθμό ~D~, βρείτε τον ελάχιστο αριθμό "κλαδέματων" που απαιτείται για να λάβετε ένα δέντρο στο οποίο ο αριθμός των λευκών κόμβων μείον τον αριθμό των μαύρων κόμβων είναι ακριβώς ~D~, ή καθορίστε ότι είναι αδύνατο να γίνει αυτό.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους ~N~ (~1 \le N \le 300~) και ~D~ (~-N \le D \le N~), που αντιπροσωπεύουν τον αριθμό των κόμβων στο δέντρο και την τιμή της απαιτούμενης διαφοράς, αντίστοιχα. Τα επόμενα ~N~ "μπλοκ" της εισόδου καθένα θα περιέχουν την περιγραφή ενός κόμβου. Η πρώτη γραμμή κάθε "μπλοκ" περιέχει τρεις ακέραιους: την ταυτότητα (id) του κόμβου (ένας μοναδικός ακέραιος μεταξύ του ~0~ και του ~N - 1~), το χρώμα του κόμβου (~1~ για έναν λευκό κόμβο, ~0~ για έναν μαύρο κόμβο) και έναν ακέραιο ~C~ που αντιπροσωπεύει τον αριθμό των παιδιών του κόμβου. Ακολουθούν ~C~ γραμμές, με καθεμία να περιέχει έναν ακέραιο πυο αντιπροσωπεύει την ταυτότητα του ενός παιδιού. Η ρίζα του δέντρου είναι ο κόμβος με ταυτότητα ~0~.

Έξοδος

Σε μία γραμμή, εκτυπώστε τον ελάχιστο αριθμό "κλαδεμάτων", όπως αναφέρθηκε στην περιγραφή του προβλήματος. Αν είναι αδύνατο να αποκτήσετε την απαιτούμενη διαφορά ~D~, εκτυπώστε -1.

Παράδειγμα

input

6 3
0 1 2
1
3
1 1 2
2
5
2 1 1
4
3 1 0
4 0 0
5 1 0

output

1