Marcus is stuck in a -dimensional grid of size , consisting of `.`

for walkable spaces and `#`

for unwalkable spaces! He is at the top left corner (position and must travel to the bottom right corner (position ) through only walkable spaces. He can **only move** left, right, and down. In a path, let be the number of times he moves down, left, and right, respectively. Let the *cost* of the path be . Marcus wants to find a path from to that has the minimum *cost*.

Marcus wants to know the minimum possible cost. Please help him!

#### Input Specification

The first line will contain the integer , the size of the grid.

The next lines will each contain characters, either `.`

for a walkable space or `#`

for an unwalkable space. The first character of the first line will be position and the character of the line will be position .

It is guaranteed positions and will be walkable (`.`

).

#### Output Specification

Output the minimum *cost* path for Marcus. If there is no path, output `-1`

.

#### Subtasks

##### Subtask 1 [25%]

##### Subtask 2 [75%]

No further constraints.

#### Sample Input

```
6
......
.#....
##.##.
......
.#####
......
```

#### Sample Output

`78`

#### Explanation For Sample

The minimum *cost* path consists of moving down units, left units, and right units, for a total of .

## Comments

Pls someone help i'm getting WA in test case 12 i dont know why. THANKS!

>:(

every

day

Marcus

strays

further

from

god's

light.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.