Selotejp

Για τον Mirko δεν υπάρχει μεγαλύτερη ευτυχία από το να βρει ένα νέο ρολό κολλητικής ταινίας, και σήμερα είναι ιδιαίτερα χαρούμενος επειδή είχε βρει το Χριστουγεννιάτικο ημερολόγιο του Slavko.

Το ημερολόγιο μπορεί να αναπαρασταθεί ως πίνακας με ~n~ γραμμές και ~m~ στήλες. Κάθε τετράγωνο περιέχει ένα μικρό παράθυρο και πίσω από κάθε παράθυρο υπάρχει ένα κομμάτι σοκολάτας. Ο Slavko είχε ήδη ανοίξει μερικά από τα παράθυρα και άλλα είναι ακόμα κλειστά.

Ο Mirko αποφάσισε να χρησιμοποιήσει την κολλητική του ταινία για να κολλήσει όλα τα κλειστά παράθυρα. Η ταινία είναι απείρως μεγάλη και έχει πλάτος ίσο με ένα κελί ημερολογίου. Ο Mirko μπορεί να σκίσει ένα κομμάτι ταινίας και να το χρησιμοποιήσει για να κολλήσει μια σειρά από οριζόντια ή κάθετα παρακείμενα κλειστά παράθυρα. Δεν θέλει να βάλει πάνω από ένα κομμάτι ταινία σε κάποιο παράθυρο, αφού θέλει να παραμείνει φίλος με τον Slavko.

Αναρωτιέται ποιος είναι ο ελάχιστος αριθμός κομματιών ταινίας που χρειάζεται για να κολλήσει όλα τα κλειστά παράθυρα.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n~ και ~m\;(1 \le n \le 1\,000,\;1 \le m \le 10)~, τις διαστάσεις του ημερολογίου.

Κάθε μία από τις ακόλουθες ~n~ γραμμές περιέχει ~m~ χαρακτήρες '.' και '#' που αντιπροσωπεύουν το ημερολόγιο. Ο χαρακτήρας '.' υποδηλώνει ένα ανοιχτό παράθυρο και ο χαρακτήρας '#' υποδηλώνει ένα κλειστό παράθυρο.

Έξοδος

Τυπώστε τον ελάχιστο αριθμό κομματιών ταινίας που χρειάζονται για να κολλήσετε όλα τα κλειστά παράθυρα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	35	Κάθε κλειστό παράθυρο βρίσκεται δίπλα σε (μοιράζεται μια πλευρά με) το πολύ δύο άλλα κλειστά παράθυρα.
2	35	~1 \le n \le 10~
3	40	Κανένας επιπλέον περιορισμός.

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

input

2 3
#.#
###

output

3

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

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

input

4 3
.#.
###
.##
.#.

output

3

input

4 4
####
#.#.
#.##
####

output

5