Police

Ο βιβλιοθηκάριος Jurica έχει ~N~ ράφια στη βιβλιοθήκη του και κάθε ράφι μπορεί να περιέχει ~M~ βιβλία. Ο Jurica είναι καλός βιβλιοθηκάριος και έτσι αποφάσισε να κάνει μια απογραφή στη βιβλιοθήκη και, αν χρειαστεί, να επιστρέψει τα βιβλία που δεν είναι στη θέση τους στη σωστή τους θέση. Μετακινεί τα βιβλία με τον εξής τρόπο:

• μετακίνηση των βιβλίων μία θέση προς τα αριστερά ή προς τα δεξιά σε ένα ράφι, εάν η θέση προς τα αριστερά ή προς τα δεξιά είναι διαθέσιμη αντίστοιχα,
• αφαίρεση ενός βιβλίου από ένα ράφι και τοποθέτησή του σε ένα διαθέσιμο μέρος σε αυτό ή σε οποιοδήποτε άλλο ράφι.

Ο προσεκτικός Jurica δεν μπορεί να μετακινήσει βιβλία αν έχει ένα βιβλίο στα χέρια του. Επιπλέον, δεν μπορεί να πάρει περισσότερα από ένα βιβλία ταυτόχρονα.

Ο Jurica έχει πόνους στην πλάτη από τότε που χρειάστηκε να μετακινήσει όλους τους τόμους της έντυπης έκδοσης της Wikipedia από τον πρώτο στον δεύτερο όροφο, οπότε τώρα θέλει να βάλει όλα τα βιβλία στη θέση τους με όσο το δυνατόν λιγότερες ανυψώσεις επειδή η πλάτη του πονάει. Ποιος είναι ο ελάχιστος αριθμός ανυψώσεων που χρειάζεται;

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N~ και ~M\;(1 \leq N \leq 1\,000,\;1 \leq M \leq 1\,000)~.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ~M~ ακέραιους αριθμούς, η ~i~-οστή γραμμή περιγράφει την τρέχουσα κατάσταση του ~i~-οστού ραφιού.

Ο αριθμός 0 υποδηλώνει ένα κενό μέρος στο ράφι και ένας αριθμός διαφορετικός από το 0 υποδηλώνει ότι υπάρχει ένα βιβλίο σε αυτό το μέρος που συμβολίζεται με αυτόν τον αριθμό. Όλα τα βιβλία σημειώνονται με διαφορετικούς αριθμούς από το 1 έως το ~K~, όπου ~K~ είναι ο συνολικός αριθμός των βιβλίων στα ράφια. Μετά από αυτό, ακολουθούν ~N~ πρόσθετες γραμμές, καθεμία από τις οποίες περιέχει ~M~ ακέραιους αριθμούς, με την ~i~-οστή γραμμή να περιγράφει την επιθυμητή κατάσταση του ~i~-οστού ραφιού.

Στην αρχική και τελική κατάσταση των ραφιών θα εμφανιστούν τα ίδια βιβλία.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~50~% των πόντων συνολικά, κάθε βιβλίο θα βρίσκεται στο ίδιο ράφι στην αρχική και τελική κατάσταση.

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

input

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

output

2

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

Ο Jurica θα μετακινήσει το βιβλίο 1 μία θέση προς τα δεξιά, στη συνέχεια θα σηκώσει το βιβλίο 2 και θα το μετακινήσει στην πρώτη θέση του πρώτου ραφιού. Σηκώνει το βιβλίο 5 και το τοποθετεί στην τέταρτη θέση στο δεύτερο ράφι.

input

3 3
1 2 3
4 5 6
7 8 0
4 2 3
6 5 1
0 7 8

output

4

input

2 2
1 2
3 4
2 3
4 1

output

-1