Minh là một chàng béo, hay nói đúng hơn là một chàng siêu siêu béo: nếu người bình thường chiếm diện tích $1\times1$ thì Minh phải chiếm diện tích $5\times5$.

Vì Minh quá béo nên di chuyển rất bất tiện. Khi chơi một số trò chơi, Minh chịu thiệt hơn nhiều so với các bạn. Bạn bè của Minh lập ra một kế hoạch giúp Minh giảm cân. Nội dung chính của kế hoạch là đưa Minh đi chơi một số trò chơi, để Minh vận động tiêu hao mỡ trong lúc chơi. Đi mê cung là một phần quan trọng của kế hoạch.

Các bạn thiết kế một mê cung, mê cung có thể coi là một ma trận gồm $n\times n$ ô vuông. Người bình thường mỗi lúc chiếm vùng $1\times1$ trong ma trận, còn Minh chiếm vùng $5\times5$. Vị trí của Minh được định nghĩa là ô chính giữa của Minh. Bốn phía xung quanh mê cung đều có vật cản. Để thuận tiện cho Minh, các bạn đặt điểm xuất phát của mê cung ở hàng $3$ cột $3$, đích ở hàng $n-2$ cột $n-2$.

Minh xuất phát tại thời điểm $0$, mỗi đơn vị thời gian có thể di chuyển lên, xuống, trái, phải một khoảng cách bằng $1$ so với vị trí hiện tại, hoặc đứng yên tại chỗ. Minh đi mê cung rất vất vả, nếu ở trong mê cung đủ lâu thì do tiêu hao nhiều mỡ, tại thời điểm $k$ Minh sẽ trở thành một người béo vừa, chỉ chiếm vùng $3\times3$. Nếu ở lâu hơn nữa, tại thời điểm $2\times k$ Minh sẽ trở thành người bình thường, chỉ chiếm vùng $1\times1$. Chú ý, khi Minh gầy đi thì điểm xuất phát và đích của mê cung không thay đổi.

Hỏi Minh cần ít nhất bao lâu để đi đến đích của mê cung. Chú ý, khi Minh đến đích thì có thể đã gầy đi hoặc chưa gầy đi.

Dữ liệu vào

Dòng đầu tiên của đầu vào chứa hai số nguyên $n$, $k$. $n$ dòng tiếp theo, mỗi dòng là một xâu gồm $n$ ký tự, ký tự + biểu thị ô trống, ký tự * biểu thị vật cản.

Dữ liệu ra

In ra một số nguyên, biểu thị đáp án.

Ví dụ

Input

9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++

Output

16

Ghi chú

Phạm vi dữ liệu

Với $30 \%$ số test, $1 \leq n \leq 50$.

Với $60 \%$ số test, $1 \leq n \leq 100$.

Với tất cả các test, $1 \leq n \leq 300$, $1 \leq k \leq 1000$.

Nguồn: Lanqiao Cup 2019 vòng chung kết quốc gia, bảng A bài F (bảng C bài I).