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:
from collections import deque
H,W=map(int,raw_input().split())
c=[]
for i in range(H):
	s=list(raw_input())
	for j in s:
		if j=="#":
			c.append(1)
		else:
			c.append(0)


nl=[ [] for i in range(H*W)]

p0=[-1,1,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
for i in range(H*W):
	if c[i]==0:
		if i==0:
			if c[i+1]==0:nl[i].append(i+1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W-1:
			if c[i-1]==0:nl[i].append(i-1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W*(H-1):
			if c[i-W]==0:nl[i].append(i-W)
			if c[i+1]==0:nl[i].append(i+1)		
		elif i==W*H-1:
			if c[i-W]==0:nl[i].append(i-W)
			if c[i-1]==0:nl[i].append(i-1)
		elif i<W-1:
			for j in p0:
				if c[i+j]==0:nl[i].append(i+j)			
		elif i%W==0:
			for j in p1:
				if c[i+j]==0:nl[i].append(i+j)	
		elif i%W==W-1:
			for j in p2:
				if c[i+j]==0:nl[i].append(i+j)
		elif i>W*(H-1):
			for j in p3:
				if c[i+j]==0:nl[i].append(i+j)
		else:
			for j in p4:
				if c[i+j]==0:nl[i].append(i+j)


V=[ None for i in range(H*W)]
d=[ float("inf") for i in range(H*W) ]

def bfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				d[i]=d[v]+1

bfs(0)

if V[H*W-1] is None:
	print -1
else:
	print H*W-(d[H*W-1]+1)-sum(c)