Kockice

Ο κ. Malnar παίζει ένα παιχνίδι με ζάρια. Οι κανόνες είναι απλοί. Αρχικά, κάθε παίκτης ρίχνει οποιονδήποτε αριθμό ζαριών. Στη συνέχεια, ο παίκτης μπορεί να επιλέξει να γυρίσει το πολύ ~k~ ζάρια, έτσι ώστε να εμφανιστούν οι πλευρές που βρίσκονται απέναντι από αυτές που είναι ορατές εκείνη τη στιγμή, ή να επιλέξει να μην γυρίσει κανένα ζάρι. Είναι γνωστό ότι οι αριθμοί σε κάθε ζεύγος απέναντι πλευρών ενός ζαριού έχουν άθροισμα ~7~ (για παράδειγμα, οι αριθμοί ~2~ και ~5~ βρίσκονται σε απέναντι πλευρές). Η βαθμολογία κάθε παίκτη είναι το άθροισμα των αριθμών που εμφανίζονται στα ζάρια αφού ολοκληρωθούν όλες οι περιστροφές. Νικητής είναι ο παίκτης με τη μεγαλύτερη βαθμολογία.

Ο κ. Malnar θέλει πολύ να κερδίσει και έτσι αποφάσισε να κλέψει. Κρυφά, τράβηξε μια φωτογραφία των ζαριών πάνω στο τραπέζι και σας την έστειλε ζητώντας βοήθεια. Η φωτογραφία έχει διαστάσεις ~3 \times n~. Επειδή τα ζάρια έχουν το ίδιο χρώμα με το τραπέζι, δεν είναι ορατά τα περιγράμματά τους. Ευτυχώς, οι κουκκίδες στα ζάρια φαίνονται καθαρά. Κάθε κουκκίδα αναπαρίσταται με ένα σύμβολο o, ενώ κάθε κενή θέση αναπαρίσταται με ένα σύμβολο -. Οι έξι πλευρές ενός ζαριού αναπαρίστανται στη φωτογραφία όπως φαίνεται παρακάτω:

---   o--   o--   o-o   o-o   o-o
-o-   ---   -ο-   ---   -ο-   ο-ο
---   --ο   --ο   ο-ο   ο-ο   o-o
 1     2     3     4     5     6

Γρήγορα! Ο κ. Malnar χρειάζεται τη βοήθειά σας! Ποια είναι η μέγιστη βαθμολογία που μπορεί να πετύχει;

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο φυσικούς αριθμούς ~n~ και ~k~ (~3 \le n \le 1000~, ~0 \le k \le 1000~), οι οποίοι αντιστοιχούν στο πλάτος της φωτογραφίας και στον μέγιστο αριθμό ζαριών που επιτρέπεται να γυρίσει ο κ. Malnar.

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

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

Έξοδος

Στην πρώτη και μοναδική γραμμή να εκτυπώσετε έναν αριθμό - τη μέγιστη βαθμολογία που μπορεί να πετύχει ο κ. Malnar.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~9~	~n = 3~
~2~	~10~	Όλα τα ζάρια εμφανίζουν είτε ~1~ είτε ~3~.
~3~	~13~	~k = 0~
~4~	~18~	Κανένας επιπλέον περιορισμός.

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

input

3 1
o-o
---
o-o

output

4

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

Ο κ. Malnar έριξε ένα ζάρι και έφερε τον αριθμό ~4~. Εφόσον ~k = 1~, ο κ. Malnar μπορεί να γυρίσει το συγκεκριμένο ζάρι. Ο αριθμός που βρίσκεται απέναντι από το ~4~ είναι το ~3~ (επειδή ~4 + 3 = 7~), επομένως, αν γυρίσει το ζάρι, θα πετύχει βαθμολογία ~3~. Ωστόσο, η βέλτιστη επιλογή είναι να μην γυρίσει το ζάρι, καθώς η βαθμολογία είναι μεγαλύτερη όταν το ζάρι εμφανίζει το ~4~ αντί για το ~3~.

input

11 4
-o-o----o--
--o------o-
-o-o------o

output

9

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

Ο κ. Malnar έριξε δύο ζάρια και έφερε τους αριθμούς ~5~ και ~3~. Μπορεί να γυρίσει έως και τέσσερα ζάρια, ωστόσο υπάρχουν μόνο δύο ζάρια πάνω στο τραπέζι, επομένως μπορεί είτε να γυρίσει το ένα ζάρι, είτε και τα δύο, είτε να μην γυρίσει κανένα.

Αν δεν γυρίσει κανένα ζάρι, θα πετύχει βαθμολογία ~5 + 3 = 8~. Αν γυρίσει μόνο το ζάρι που εμφανίζει το ~5~, η τιμή του θα αλλάξει σε ~2~, με αποτέλεσμα η βαθμολογία του να γίνει ~2 + 3 = 5~. Αν γυρίσει μόνο το ζάρι που εμφανίζει το ~3~, η τιμή του θα αλλάξει σε ~4~, με αποτέλεσμα η βαθμολογία του να γίνει ~4 + 5 = 9~. Αν γυρίσει και τα δύο ζάρια, αυτά θα εμφανίζουν τους αριθμούς ~2~ και ~4~, με αποτέλεσμα η βαθμολογία του να γίνει ~2 + 4 = 6~.

Επομένως, η μέγιστη βαθμολογία που μπορεί να πετύχει είναι ~9~ - αυτό επιτυγχάνεται γυρίζοντας το ζάρι που εμφανίζει το ~3~.

input

17 2
o--o-o-------o---
-o-o-o--o--------
--oo-o---------o-

output

20

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

Ο κ. Malnar έριξε τέσσερα ζάρια και έφερε, με τη σειρά που εμφανίζονται στη φωτογραφία, τους αριθμούς ~3~, ~6~, ~1~ και ~2~. Μπορεί να γυρίσει το πολύ δύο από αυτά. Η μέγιστη βαθμολογία επιτυγχάνεται αν γυρίσει το ζάρι που εμφανίζει το ~1~ (το οποίο μετατρέπεται σε ~6~) και το ζάρι που εμφανίζει το ~2~ (το οποίο μετατρέπεται σε ~5~).

Με αυτόν τον τρόπο, η βαθμολογία του αλλάζει από ~3 + 6 + 1 + 2 = 12~ σε ~3 + 6 + 6 + 5 = 20~.