Trip Navigator is a four-player minigame in Super Mario Party, and you can view how the game is actually played here. The game uses a square playground, which is divided into four areas for the four players. Each player will need to start from a corner of the playground, and arrive at the center as quickly as possible. For example, player one will start from the top left corner, and need to arrive at the bottom right of their own area, which is the center of the entire playground. The area is littered with many banana peels. Every time a player slips a banana peel, they are stunned for a while.

At the beginning of the game, the players will have a bird-eye view of their own area. This way they can be prepared for the banana peels on the way. Assume you are player 1. Your area can be modeled as an ~n \times n~ grid. You will start from the top-left cell ~(0, 0)~, and your destination is the bottom right cell ~(n-1, n-1)~. Each cell will either be empty or have a banana peel. A player can move from the current cell to any of its adjacent cells (the one to its top, bottom, left or right), which takes 1 second. If the cell that a player moves to has a banana peel, the player will be stunned at that cell for ~t~ seconds, which means the player cannot leave (i.e., cannot move out of) the banana peel cell for ~t~ seconds. Your starting and destination cells are always without banana peels. Given the playground and all the bananas, your task is to compute the minimum time to arrive at the destination. You only need to report the shortest time one needs to arrive at the destination (the bottom right cell) from the starting point (the top left cell).

Input Specification

The first line of the input contains two integers, ~n~ (~0 \le n \le 10^3~), which means the area will be described as an ~n \times n~ matrix, and ~t~ (~0 \le t \le 10^3~), which is the amount of time a player will be stunned for.

Output Specification

The output only contains 1 integer, which is the shortest time the player needs to arrive at their destination (the bottom right cell).

Sample Input

5 3
-b--b
-bb--
--bb-
--bbb
b-bb-

Sample Output

14

Explanation for Sample Output

For the first test case, one of the best solutions is as follows:

down - down - down - right - down - right (stunned for 3 seconds) - right (stunned for 3 seconds) - right (arrive)

The total time is 14s.

There are also other routes that can finish in 14s.

Source of pictures and descriptions: https://www.mariowiki.com/Trip_Navigator. You can also find more details about the game from this site.

Scoring

For 25% of the test cases, ~n \le 50~.

For 50% of the test cases, ~n \le 300~.

There are 20 test cases, 5 points each.