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:
from collections import deque

H,W=map(int,input().split())
p={}
for i in range(H):    
    for j,c in enumerate(input()):
        p[(i,j)]=c=='.'
d={(i,j):-1 for i in range(H) for j in range(W)}
white=sum(p.values())
q=deque()
s=(0,0)
q.append(s);d[s]=1
while q:
    u=q.popleft()
    ui,uj=u
    for v in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        vi,vj=v
        if 0<=vi<=H-1 and 0<=vj<=W-1 and p[v] and d[v]==-1:
            d[v]=d[u]+1
            q.append(v)
if d[(H-1,W-1)]==-1:
    ans=-1
else:
    ans=white-d[(H-1,W-1)]
print(ans)