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.Scanner;

public class Main {

	public static String[] s;
	public static int[][] dis;
	public static int h;
	public static int w;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		h = sc.nextInt();
		w = sc.nextInt();
		s = new String[h];
		for(int i = 0; i < h; i++) {
			s[i] = sc.next();
		}
		dis = new int[h][w];
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				dis[i][j] = Integer.MAX_VALUE;
			}
		}
		dis[0][0] = 1;
		djk(0, 0);
		if(dis[h - 1][w - 1] == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			int cnt = 0;
			for(int i = 0; i < h; i++) {
				for(int j = 0; j < w; j++) {
					if(s[i].charAt(j) == '#')
						cnt++;
				}
			}
			int ans = h * w - cnt - dis[h - 1][w - 1];
			System.out.println(ans);
		}
	}

	public static void djk(int i, int j) {
		int tmp = dis[i][j];
		if(i > 0 && dis[i - 1][j] > tmp + 1 && s[i].charAt(j) == '.') {
			dis[i - 1][j] = tmp + 1;
			djk(i - 1, j);
		}
		if(i < h - 1 && dis[i + 1][j] > tmp + 1 && s[i + 1].charAt(j) == '.') {
			dis[i + 1][j] = tmp + 1;
			djk(i + 1, j);
		}
		if(j > 0 && dis[i][j - 1] > tmp + 1 && s[i].charAt(j - 1) == '.') {
			dis[i][j - 1] = tmp + 1;
			djk(i, j - 1);
		}
		if(j < w - 1 && dis[i][j + 1] > tmp + 1 && s[i].charAt(j + 1) == '.') {
			dis[i][j + 1] = tmp + 1;
			djk(i, j + 1);
		}
	}

}

class Pair {
	private int i;
	private int j;

	protected Pair(int i, int j) {
		super();
		this.i = i;
		this.j = j;
	}

	public int getI() {
		return i;
	}

	public void setI(int i) {
		this.i = i;
	}

	public int getJ() {
		return j;
	}

	public void setJ(int j) {
		this.j = j;
	}

}