Zmija

Ο Mirko φτιάχνει έναν κλώνο του δημοφιλούς παιχνιδιού υπολογιστή "Φιδάκι". Στο παιχνίδι, ελέγχετε την κίνηση ενός φιδιού σε μια οθόνη με διαστάσεις ~R \times S~ pixel. Ο στόχος του παιχνιδιού είναι να μαζευτούν όλα τα μήλα.

Δυστυχώς, η υλοποίηση του Mirko δεν είναι τόσο καλή και το gameplay είναι διαφορετικό από το πρωτότυπο. Ακολουθεί μια περιγραφή του παιχνιδιού του Mirko:

• Σε αντίθεση με το πρωτότυπο, τα μήλα δεν εμφανίζονται τυχαία στην οθόνη, αλλά αντιθέτως γνωρίζετε τις θέσεις όλων των μήλων στην αρχή του παιχνιδιού
• στην αρχή του παιχνιδιού, το φίδι βρίσκεται στο κάτω αριστερό pixel της οθόνης και είναι στραμμένο προς τα δεξιά
• υπάρχουν δύο κουμπιά στο παιχνίδι, που συμβολίζονται με ~A~ και ~B~
• όταν πατάτε το κουμπί ~A~, το φίδι κινείται προς τα εμπρός κατά 1 pixel προς την κατεύθυνση που βλέπει αυτήν τη στιγμή. Αν αυτή η κίνηση θα προκαλούσε το φίδι να βγει εκτός οθόνης, δεν θα συμβεί τίποτα.
• όταν πατάτε το κουμπί ~B~, το φίδι ανεβαίνει κατά 1 pixel και αλλάζει την κατεύθυνση που κοιτάζει κατά 180°
• όταν το φίδι μετακινείται σε ένα pixel που περιέχει ένα μήλο, τρώει το μήλο αλλά δεν μεγαλώνει όπως στο αρχικό παιχνίδι

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~R~ και ~S\;(2 \leq R,\;S \leq 1\,000)~, το ύψος και το πλάτος της οθόνης.

Κάθε μία από τις ακόλουθες ~R~ γραμμές περιέχει ακριβώς ~S~ χαρακτήρες. Αυτοί οι χαρακτήρες αντιπροσωπεύουν το περιεχόμενο της οθόνης. Τα εικονοστοιχεία με μήλα επάνω τους συμβολίζονται με "~J~" και τα κενά εικονοστοιχεία με "." .

Η κάτω αριστερή γωνία περιέχει τον χαρακτήρα "~Z~" που αντιπροσωπεύει το φίδι στην αρχική του θέση.

Έξοδος

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

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

input

5 5
...J.
.....
J..J.
J....
Z....

output

7

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

Η συντομότερη ακολουθία πιέσεων κουμπιών που χρειάζεται για να μαζέψει το φίδι όλα τα μήλα είναι το ~BBAAABB~.

input

5 5
.....
J...J
.J.J.
.JJJ.
Z....

output

15

input

3 4
...J
....
Z....

output

5