Lubenica

Τα παιδιά στο σχολείο διασκεδάζουν αντί να ακούν τον δάσκαλο. Με τις συσκευές τους iPhone τα παιδιά πετούν καρπούζια μεταξύ τους στον ιστότοπο κοινωνικής δικτύωσης Facebook.
Το παιχνίδι ξεκίνησε όταν ο Goran πέταξε ένα καρπούζι σε κάθε φίλο του κατά τη διάρκεια του πρώτου μαθήματος εκείνης της ημέρας. Κατά τη διάρκεια των επόμενων μαθημάτων, όλα τα παιδιά (συμπεριλαμβανομένου του Goran) συμπεριφέρθηκαν ως εξής:
 • Αν είχαν χτυπηθεί από μονό αριθμό καρπουζιών κατά τη διάρκεια του προηγούμενου μαθήματος, έριχναν ακριβώς
  ένα καρπούζι σε κάθε φίλο τους.
 • Αν είχαν χτυπηθεί από ζυγό αριθμό καρπουζιών (συμπεριλαμβανομένου του μηδενός), τότε χτυπούσαν το καθένα από
  τους φίλους τους με δύο καρπούζια.
Τα παιδιά αριθμούνται από το ~1~ έως το ~N~, ο Goran είναι προφανώς ο αριθμός 1. Οι φιλικές σχέσεις μεταξύ των παιδιών είναι επίσης γνωστές.
Γράψτε ένα πρόγραμμα που θα υπολογίζει τον συνολικό αριθμό των καρπουζιών που πετάχτηκαν μετά από ~H~ μαθήματα.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~H (1 \le N \le 20,\; 1 \le H \le 1\,000 \,000\,000)~, τον αριθμό των παιδιών και μαθημάτων.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει μια σειρά από ~N~ χαρακτήρες '0' ή '1'. Ο χαρακτήρας ~(A,\,B)~ σε αυτό τον πίνακα είναι '1' εάν τα παιδιά ~A~ και ~B~ είναι φίλοι.
Κανένα παιδί δεν θα είναι φίλος του εαυτού του. Ο πίνακας εισόδου θα είναι συμμετρικός.

Έξοδος

Τυπώστε των αριθμό των καρπουζιών μετά από ~H~ μαθήματα.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~50~% των πόντων, το ~H~ θα είναι το πολύ ~1\,000~

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

input

4 1
0110
1001
1001
0110

output

2

input

4 2
0110
1001
1001
0110

output

14

input

5 3
01000
10110
01000
01001
00010

output

26

Στο δεύτερο παράδειγμα, ο Goran ρίχνει δύο καρπούζια κατά τη διάρκεια του πρώτου μαθήματος. Κατά τη διάρκεια του δεύτερου μαθήματος, τα παιδιά 1 και 4 το καθένα ρίχνουν δύο καρπούζια στα 2 και 3 το καθένα, ενώ τα 2 και 3 ρίχνουν ένα καρπούζι στο 1 και 4. Συνολικά ρίχνονται 12 καρπούζια κατά τη διάρκεια του δεύτερου μαθήματος.