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 PYTHON):

Solution:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
L = [list(input().strip()) for _ in range(N)]

m = [[10 ** 18 for _ in range(M)] for _ in range(N)]

def bfs(x, y, c):
    if L[x][y] == "#":
        return

    if m[x][y] <= c:
        return

    m[x][y] = c

    if x + 1 < N:
        bfs(x + 1, y, c + 1)

    if y + 1 < M:
        bfs(x, y + 1, c + 1)

    if x - 1 >= 0:
        bfs(x - 1, y, c + 1)

    if y - 1 >= 0:
        bfs(x, y - 1, c + 1)

bfs(0, 0, 0)

if m[-1][-1] == 10 ** 18:
    print(-1)
    exit()

def dfs(x, y, c):
    if x == 0 and y == 0:
        L[x][y] = "o"
        return True
    for (_x, _y) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if x + _x < N and x + _x >= 0 and y + _y < M and y + _y >= 0:
            if c - 1 == m[x + _x][y + _y]:
                if dfs(x + _x, y + _y, c - 1):
                    L[x][y] = "o"
                    return True
    return False

dfs(N - 1, M - 1, m[-1][-1])

ans = 0
for v in L:
    ans += len([0 for c in v if c == "."])

print(ans)