Bad Codes

Ο φίλος σας έχεο κατασκευάσει έναν κώδικα τον οποίο θέλει να χρησιμοποιήσει για να σας στέλνει μυστικά μηνύματα. Τα μηνύματα θα αποτελούνται μόνο από ~N~ διαφορετικά σύμβολα και κάθε σύμβολο θα αντιστοιχεί σε μία δυαδική ακολουθία με το πολύ ~M~ bit.

Ωστόσο, δεν είστε σίγουροι ότι ο κώδικας θα λειτουργήσει: υπάρχει μία πιθανότητα μία δυαδική ακολουθία να μπορεί να αντιστοιχεί σε δύο (ή περισσότερα) διαφορετικά μηνύματα.

Για παράδειγμα, αν ο κώδικας ήταν:

   A -> 101
   B -> 10
   C -> 1
   D -> 100

τότε η δυαδική ακολουθία ~101~ θα μπορούσε να αντιστοιχεί είτε στο ~A~ είτε στο ~BC~.

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

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο, χωρισμένους με κενό, ακέραιους ~N~ και ~M~ (~1~ ~\le~ ~N~, ~M~ ~\le~ ~50~). Οι επόμενες ~N~ γραμμές της εισόδου θα έχουν η καθεμία τουλάχιστον έναν και το πολύ ~M~ χαρακτήρες από το σύνολο {~0~, ~1~}.

Βαθμολογία

Για ~4~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ = ~4~ και ~M~ ~\le~ ~6~.

Για επιπλέον ~7~ από τους ~25~ διαθέσιμους βαθμούς κάθε μία από τις δυαδικές ακολουθίες ακριβώς ένα ~1~ bit. Για παράδειγμα, οι ακολουθίες ~00100~ ή ~1000~ θα ήταν έγκυρες σε αυτή την περίπτωση.

Έξοδος

Η έξοδος θα έχει μήκος μίας γραμμής.

Αν υπάρχει μία δυαδική ακολουθία που αντιστοιχεί σε δύο (ή περισσότερα) μηνύματα, εκτυπώστε τη μικρότερη τέτοια ακολουθία, αλλιώς, εκτυπώστε μία γραμμή που να περιέχει το -1.

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

input

4 3
101
10
1
100

output

3

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

Αυτό είναι το παράδειγμα από την περιγραφή του προβλήματος.

input

4 4
1011
1000
1111
1001

output

-1

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

Δεν υπάρχει κάποια δυαδική ακολουθία που να αντιστοιχεί σε πάνω από ένα μήνυμα. Προσέξτε ότι μιας και κάθε κώδικας είναι ~4~ bit και κανένας δεν είναι ο ίδιος, κάθε κωδικοποίηση από ~4k~ bit μπορεί να αποκωδικοποιηθεί μοναδικά σε ~k~ χαρακτήρες.