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:
import Queue
def main():
    H,W=map(int,raw_input().split())
    s=[raw_input() for i in range(H)]
    q=Queue.Queue()
    visited=[[False]*W for _ in range(H)]
    dist=[[1145141919810]*W for _ in range(H)]
    visited[0][0]=True
    dist[0][0]=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    q.put((0,0))

    while not q.empty():
        x,y=q.get()
        for i in range(4):  
            xx=x+dx[i]
            yy=y+dy[i]
            if (not 0<=xx<H) or (not 0<=yy<W): continue
            if s[xx][yy] == "#" :continue
            if visited[xx][yy]:continue
            visited[xx][yy]=True
            dist[xx][yy]=dist[x][y]+1
            q.put((xx,yy))
    if not visited[H-1][W-1]:
        print(-1)
        return
    use=[[False]*W for _ in range(H)]
    use[H-1][W-1]=True
    use[0][0]=True
    (x,y)=(H-1, W-1)
    while (x,y) != (0,0):
        use[x][y]=True
        mpos=(-1,-1)
        mval=1145141919
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]
            if (not 0<=xx<H) or (not 0<=yy<W): continue     
            if dist[xx][yy] < mval:
                mpos=(xx,yy)
                mval=dist[xx][yy]
        x,y=mpos
    cnt=0
    for x in range(H):
        for y in range(W):
            if s[x][y] == "." and not use[x][y]: cnt+=1
    print(cnt)
main()