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.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int h = sc.nextInt();
		int w = sc.nextInt();

		board = new char[h][w];
		dist = new int[h][w];
		visit = new boolean[h][w];

		int block = 0;
		for(int i = 0; i < h; i++){
			String str = sc.next();

			for(int j = 0; j < w; j++){
				board[i][j] = str.charAt(j);
				if(board[i][j] == '#'){
					block++;
				}
			}

//			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}

		ArrayList<Point2D> queue = new ArrayList<Point2D>();

		visit[0][0] = true;
		dist[0][0] = 1;
		queue.add(new Point2D.Double(0, 0));

		int dx[] = {0,1,0,-1};
		int dy[] = {1,0,-1,0};
		while(!queue.isEmpty()){
			Point2D point = queue.remove(0);

			for(int i = 0; i < 4; i++){
				int tmpX = (int)point.getX() + dx[i];
				int tmpY = (int)point.getY() + dy[i];

				if(tmpX < 0 || tmpX >= w || tmpY < 0 || tmpY >= h || board[tmpY][tmpX] == '#'){
					continue;
				}

				if(!visit[tmpY][tmpX]){
					visit[tmpY][tmpX] = true;
					dist[tmpY][tmpX] = dist[(int)point.getY()][(int)point.getX()] + 1;
					queue.add(new Point2D.Double(tmpX, tmpY));
				}
			}
		}

//		for(int i = 0; i < h; i++){
//			for(int j = 0; j < w; j++){
//				System.out.print(dist[i][j] + " ");
//			}
//			System.out.println();
//		}

		System.out.println(dist[h - 1][w - 1] != 0 ? h*w - block - dist[h - 1][w - 1] : -1);

	}

	static char[][] board;
	static int[][] dist;
	static boolean[][] visit;

}