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:
#abc088d

H,W=map(int,raw_input().split())
maze=[]
for i in xrange(H):
 maze.append(list(raw_input()))
d=[[-1 for i in xrange(W+1)] for j in xrange(H+1)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
 q=[]
 q.insert(0,(0,0))
 d[sx][sy]=0
 while len(q):
  x,y=q.pop()
  if x==gx and y==gy:
   break
  for i in xrange(4):
   nx,ny=x+dx[i],y+dy[i]
   if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='#' and d[nx][ny]==-1:
    q.insert(0,(nx,ny))
    d[nx][ny]=d[x][y]+1
 return d[gx][gy]
sx,sy=0,0
gx,gy=H-1,W-1

def cntsharp():
 cnt=0
 for i in xrange(H):
  cnt+=maze[i].count('#')
 return cnt
if bfs()==-1:
 print -1
else:
 print H*W-(bfs()+cntsharp())-1