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.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public class Node {
		int score;
		int x;
		int y;
		public Node(int score, int x, int y) {
			super();
			this.score = score;
			this.x = x;
			this.y = y;
		}
		
		
	}

	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();

		char[][] s = new char[h][];
		for (int i = 0; i < h; i++) {
			s[i] = sc.next().toCharArray();
		}
    	Deque<Node> queue = new ArrayDeque<>();
        queue.add(new Node(1,0,0));
        
        int b = 0;
        Node node; 
        while( (node = queue.poll()) != null ) {
        	int score = node.score;
        	int x = node.x;
        	int y = node.y;
        	if( x<0 || w<=x || y<0 || h<=y )
        		continue;
        	if( s[y][x]!='.')
        		continue;
        	s[y][x] = '/';
        	
            boolean isGoal = x == w-1 && y == h-1;
			if( isGoal ) {
				for (int i = 0; i < h ; i++) {
					for (int j = 0; j < w ; j++) {
						if( s[i][j] != '#' )
							b++;
					}
				}
				System.out.println( b - node.score );
				return ;
            }
			
			// 
	        queue.add(new Node(score+1, x+1, y ));
	        queue.add(new Node(score+1, x-1, y ));
	        queue.add(new Node(score+1, x, y+1 ));
	        queue.add(new Node(score+1, x, y-1 ));

        }

		System.out.println(-1);
	}
	
    
}