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())
l=[]
l.append(['#' for i in range(w+2)])
for i in range(h):
  l.append(list('#'+input()+'#'))
l.append(['#' for i in range(w+2)])
ctw=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='.':ctw+=1
L=[[1,1]]
ct=0
x=0
for i in range(h*w):
  L2=[]
  for j in range(len(L)):
    L3=[[L[j][0]-1,L[j][1]],[L[j][0]+1,L[j][1]],[L[j][0],L[j][1]-1],[L[j][0],L[j][1]+1]]
    for k in range(4):
      if l[L3[k][0]][L3[k][1]]=='.':
        L2.append(L3[k])
        l[L3[k][0]][L3[k][1]]='#'
  ct+=1
  L=L2
  if [h,w] in L:
    x=ct
    break
if x==0:print(-1)
else:print(ctw-ct-1)