Vuk

Ο λύκος που τον λέγαν Vjekoslav, τρέχει μακριά από ένα σωρό κυνηγούς που διψούν για αίμα. Οι κυνηγοί είναι έξυπνοι και κρύβονται πίσω από δέντρα. Ο Vjekoslav το γνωρίζει αυτό, αλλά δεν ξέρει πίσω από ποια δέντρα κρύβονται. Θέλει να τρέξει στο άνετο και -πολιτισμένο- καλύβι του (σε αντίθεση με το απολίτιστο λημέρι των κυνηγών, ναι σε αυτό το σημείο εκφράζω την υποστήριξη μου προς τους λύκους), μένοντας όσο πιο μακριά γίνεται από τα δέντρα.
Το δάσος μπορεί να αναπαρασταθεί ως ένα πλέγμα ~N~ επί ~M~. Ας συμβολίσουμε τα χωρισμένα τμήματα του λιβαδιού του δάσους που εχουν σκέτη χλόη με '~.~', τα τμήματα που έχουν ένα δέντρο στη μέση τους με '~+~', την τωρινή θέση του Vjekoslav του λύκου με '~V~' και τη θέση του καλυβιού του με '~J~'. Ο Vjekoslav μπορεί να τρέξει από το τωρινό του τμήμα σε οποιοδήποτε άλλο τμήμα νότια, ανατολικά, βόρεια ή δυτικά του, ακόμη κι αν αυτό περιέχει δέντρο.
Αν ο Vjekoslav στέκεται στην ~R~-οστή γραμμή και στην ~C~-οστή στήλη στο πλέγμα και υπάρχει ένα δέντρο στην ~A~-οστή γραμμή και στην ~B~-οστή στήλη τότε η απόσταση μεταξύ του Vjekoslav και του δέντρου είναι:

~|R - A| + |C - B|~

Βοηθήστε τον Vjekoslav να βρει την καλύτερη διαδρομή ως το καλύβι του. Η καλύτερη διαδρομή είναι οποιαδήποτε διαδρομή μεγιστοποιεί την ελάχιστη απόσταση μεταξύ του Vjekoslav και όλων των δέντρων ανά δεδομένη στιγμή.
Σημείωση: το εξοχικό του Vjekoslav δεν καταλαμβάνει ολόκληρο το τμήμα στο οποίο βρίσκεται, έτσι αυτό το τμήμα πρέπει επίσης να περιλαμβάνεται στη διαδρομή.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~N~ και ~M~ για τις διαστάσεις του πλέγματος, όπου ~(1 \le N,\; M \le 500) ~.
Οι επόμενες ~N~ γραμμές περιέχουν ~M~ το πλήθος χαρακτήρες ή καθεμιά: '~.~', '~+~', '~V~', '~J~'.
Η είσοδος θα περιέχει ακριβώς μία φορά τους χαρακτήρες '~V~' και '~J~' και τουλάχιστον έναν χαρακτήρα '~+~'.

Έξοδος

Εκτυπώστε έναν μόνο ακέραιο αριθμό, την ελάχιστη απόσταση από ένα δέντρο στην ιδανική διαδρομή.

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

input

4 4
+...
....
V..J

output

3

input

4 5
.....
.+++.
.+.+.
V+.J+

output

0