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 JAVA):

Solution:


import java.util.LinkedList;
import java.util.Scanner;
public class Main {
	private static class Pair{
		private int key;
		private int value;
		public Pair(int key,int value)
		{
			this.key=key;
			this.value=value;
		}
		public int getKey()
		{
			return key;
		}
		public int getValue()
		{
			return value;
		}
	}
		public static int boardBfs(char[][] a)
		{
			LinkedList<Pair> q = new LinkedList<Pair>();
			boolean[][] visited = new boolean[a.length][a[0].length];
			Pair[][] prev = new Pair [a.length][a[0].length];
			q.add(new Pair(0,0));
			visited[0][0]=true;
			int[] row = {0,0,1,-1};
			int[] col = {-1,1,0,0};
			
			while(!q.isEmpty())
			{
				Pair p = q.pop();
				int n=(int) p.getKey();
				int m=(int) p.getValue();
				
				if(n==a.length-1 && m==a[0].length-1)
				{
					//finish the bfs
					int count = 0;
					Pair pair = prev[n][m];
					n=(int)pair.getKey();
					m=(int)pair.getValue();
					while(n!=0 || m!=0)
					{
						a[n][m]='#';
					    pair = prev[n][m];
						n = (int)pair.getKey();
						m = (int) pair.getValue();
					}
					//count 
					for(int i=0;i<a.length;i++)
					{
						for(int j=0;j<a[0].length;j++)
						{
							if(a[i][j]=='.')
								count++;
						}
					}
					return count-2;
				}
				for(int i=0;i<row.length;i++)
				{
					if(n+row[i]>=0&&n+row[i]<a.length&&m+col[i]>=0&&m+col[i]<a[0].length&&
							a[n+row[i]][m+col[i]]=='.'&& !visited[n+row[i]][m+col[i]])
					{
						//add to bfs 
						visited[n+row[i]][m+col[i]]=true;
						prev[n+row[i]][m+col[i]]=p;
						q.add(new Pair(n+row[i],m+col[i]));
					}
				}			
			}
			
			return -1;
		}
		
		public static void main(String[] args){
			
			Scanner s = new Scanner(System.in);
			int n=s.nextInt();
			int m=s.nextInt();
			char[][] a = new char[n][m];
			
			for (int i = 0; i < a.length; i++) {
				String str = s.next();
				for (int j = 0; j < a[0].length; j++) 
					a[i][j]=str.charAt(j);
			}
			System.out.println(boardBfs(a));
					
			s.close();
		}		
}