Pyramid Message Scheme

Η Spamway Inc. διατηρεί ένα δίκτυο υπολογιστών ζόμπι για να ζητά και να συλλέγει παραγγελίες για διάφορα εκλεκτά προϊόντα της. Κάθε υπολογιστής ζόμπι είναι υπεύθυνος για μηδέν ή περισσότερα δευτερεύοντα ζόμπι που συντονίζει σε αυτές τις δραστηριότητες.

Η Spamway χρησιμοποιεί μια απλή στρατηγική επικοινωνίας μεταξύ των ζόμπι της για τη μετάδοση ζήτησης και τη λήψη παραγγελιών. Κάθε προσελκυτική ενέργεια προέρχεται από το ζόμπι επικεφαλής της Spamway, το οποίο στη συνέχεια το κοινοποιεί σε καθέναν από τους υφισταμένους του με τη σειρά, περιμένοντας να συλλέξει εντολές από έναν υφιστάμενο πριν προχωρήσει στον επόμενο. Κάθε υφιστάμενος χρησιμοποιεί την ίδια στρατηγική - στέλνει και λαμβάνει από κάθε έναν από τους υφισταμένους του με τη σειρά του.

Για παράδειγμα, ας υποθέσουμε ότι το Home (ζόμπι επικεφαλής) έχει δύο υφιστάμενα ζόμπι, που ονομάζονται Alfred και Betty. Οι υφιστάμενοι του Alfred ονομάζονται Cindy και Dennis. Η Betty δεν έχει υφισταμένους. Αυτή η οργάνωση φαίνεται παρακάτω.

Ο Home στέλνει πρώτα στον Alfred. Στη συνέχεια ο Alfred στέλνει στη Cindy. Η Cindy απαντά στον Alfred. Ο Alfred στέλνει στον Dennis. Ο Dennis απαντά στον Alfred. Ο Alfred απαντά στον Home. Ο Home στέλνει στην Betty. Η Betty απαντά στον Home.

Κάθε μήνυμα διαρκεί ~10~ δευτερόλεπτα για να παραδοθεί. Έτσι το παράδειγμα που δίνεται παραπάνω θα ολοκληρωθεί σε ~80~ δευτερόλεπτα. Έχετε κρατηθεί από την Spamway, η οποία θα σας πληρώσει αδρά (σε Spam Bucks, που μπορούν να εξαργυρωθούν για οποιοδήποτε από τα πολύτιμα προϊόντα της) για να τους βοηθήσετε να μειώσουν τον χρόνο που απαιτείται για την προσελκυτική ενέργεια και τη συλλογή παραγγελιών. Συγκεκριμένα, η Spamway εξετάζει μια νέα στρατηγική στην οποία κάθε ζόμπι στέλνει μηνύματα σε κάθε υφιστάμενό του και περιμένει τις απαντήσεις τους μόνο αφού σταλούν όλα τα μηνύματα.

Ο διαχειριστής του δικτύου της Spamway έχει καταγράψει μια χρονολογική λίστα με το όνομα του παραλήπτη κάθε μηνύματος που εμπλέκεται σε μια συγκεκριμένη προσελκυτική ενέργεια. Για το παραπάνω παράδειγμα, χρησιμοποιώντας την αργή στρατηγική, αυτή η λίστα θα είναι: Alfred, Cindy, Alfred, Dennis, Alfred, Home, Betty, Home. (Σημειώστε ότι ~8~ μηνύματα, στα ~10~ δευτερόλεπτα ανά μήνυμα, είναι συνολικά ~80~ δευτερόλεπτα.)

Χρησιμοποιώντας τη νέα και βελτιωμένη στρατηγική, ο Home στέλνει στον Alfred και την Betty ταυτόχρονα, ο Alfred στέλνει στη Cindy και τον Dennis την ίδια στιγμή που η Betty απαντά, η Cindy και ο Dennis απαντούν ταυτόχρονα στον Alfred και τελικά ο Alfred απαντά στον Home. Χρησιμοποιώντας τη νέα στρατηγική, η Spamway χρειάζεται μόνο ~40~ δευτερόλεπτα για να ολοκληρώσει την επικοινωνία που διαρκεί ~80~ δευτερόλεπτα χρησιμοποιώντας την παλιά στρατηγική. Έτσι, η Spamway μπορεί να στείλει διπλάσιες προσελκυτικές ενέργειες και να βγάζοντας διπλάσια χρήματα.

Είσοδος

Ως είσοδος, σας δίνονται λίστες ονομάτων που περιγράφουν τη σειρά λήψης των μηνυμάτων χρησιμοποιώντας την παλιά στρατηγική Spamway. Η είσοδος περιέχει τον ακέραιο ~L~, ακολουθούμενο από ~L~ λίστες μηνυμάτων. Κάθε λίστα ξεκινά με έναν ακέραιο, ~n~, που προσδιορίζει τον αριθμό των παραληπτών του μηνύματος στη λίστα, ακολουθούμενο από ~n~ γραμμές, καθεμία από τις οποίες περιέχει το όνομα ενός παραλήπτη μηνύματος.

Έξοδος

Για κάθε λίστα πρέπει να εκτυπώσετε έναν ακέραιο αριθμό που υποδεικνύει τον χρόνο σε δευτερόλεπτα που κερδίζει το Spamway.

Παράδείγμα

input

1
8
Alfred
Cindy
Alfred
Dennis
Alfred
Home
Betty
Home

output

40