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:
a=map(int, raw_input().split())
lis=[]
for i in range(a[0]):
    b=list(raw_input())
    lis.append(b)

pro=[]
cou=0
for i in range(a[0]):
    pre=[]
    for j in range(a[1]):
        if lis[i][j]=="#":
            cou+=1
        pre.append(2501)
    pro.append(pre)

while True:
    ch=0
    for i in range(a[0]):
        for j in range(a[1]):
            if lis[i][j]==".":
                if i==0:
                    if j==0:
                        pro[i][j]=1
                    elif j==a[1]-1:
                        u = 2501
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = 2501
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                elif i==a[0]-1:
                    if j==0:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = 2501
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                else:
                    if j==0:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j+ 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
    if ch==0:
        break
if pro[a[0]-1][a[1]-1]==2501:
    print -1
else:
    print a[0]*a[1]-cou-pro[a[0]-1][a[1]-1]