Problem: Constraints

* H is an integer between 2 and 50 (inclusive).
* W is an integer between 2 and 50 (inclusive).
* s_{i, j} is `.` or `#` (1 \leq i \leq H, 1 \leq j \leq W).
* s_{1, 1} and s_{H, W} are `.`.

Input

Input is given from Standard Input in the following format:


H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
:   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}


Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Examples

Input

3 3
..#
#..
...


Output

2


Input

3 3
..#
..
...


Output

2


Input

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................


Output

209

Solution (in PYTHON3):

Solution:
H,W = map(int,input().split())
s = [["#"]*(W+2)] + [["#"] + [c for c in input()] + ["#"] for _ in [0]*H] + [["#"]*(W+2)]
ans = sum([sum([int(c == ".") for c in row]) for row in s])
s[1][1] = 1
ij = [[1,1]]
d = [[0,1],[0,-1],[1,0],[-1,0]]
cnt = 0
while ij[cnt:]:
    i,j = ij[cnt]
    for di,dj in d:
        if s[i+di][j+dj] == ".":
            s[i+di][j+dj] = s[i][j] + 1
            ij.append([i+di,j+dj])
            if i+di == H and j+dj == W:
                break
    cnt += 1
if s[H][W] == ".":
    ans = -1
else:
    ans -= s[H][W]
print(ans)