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 void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner stdin = new Scanner(System.in);

		int inH = stdin.nextInt();
		int inW = stdin.nextInt();

		char[][] grid = new char[inH][];
		int white = 0;
		for (int h = 0; h < inH; h++) {
			grid[h] = stdin.next().toCharArray();
			for (int w = 0; w < inW; w++) {
				if (grid[h][w] == '.') {
					white++;
				}
			}
		}

		int[][] act = new int[inH][inW];
		int updateCount = 0;
		while ((act[0][0] == 0) && (updateCount < (inH * inW))) {
			act = getNextAct(act, grid, inH, inW);
			updateCount++;
		}

		if (updateCount == (inH * inW)) {
			System.out.println(-1);
			return;
		}

		int moveCount = 1;
		int h = 0;
		int w = 0;

		while ((h != (inH - 1)) || (w != (inW - 1))) {
			int nextH = h;
			int nextW = w;
			int max = act[h][w];

			if (((h - 1) >= 0) && (act[h - 1][w] > max)) {
				max = act[h - 1][w];
				nextH = h - 1;
				nextW = w;
			}
			if (((h + 1) < act.length) && (act[h + 1][w] > max)) {
				max = act[h + 1][w];
				nextH = h + 1;
				nextW = w;
			}
			if (((w - 1) >= 0) && (act[h][w - 1] > max)) {
				max = act[h][w - 1];
				nextH = h;
				nextW = w - 1;
			}
			if (((w + 1) < act[h].length) && (act[h][w + 1] > max)) {
				max = act[h][w + 1];
				nextH = h;
				nextW = w + 1;
			}

			h = nextH;
			w = nextW;
			moveCount++;
		}

		System.out.println(white - moveCount);
	}

	private static int[][] getNextAct(int[][] act, char[][] grid, int sizeH, int sizeW) {
		int[][] next = new int[sizeH][sizeW];
		for (int h = 0; h < sizeH; h++) {
			for (int w = 0; w < sizeW; w++) {
				next[h][w] = getUpdateAct(act, grid, sizeH, sizeW, h, w);
			}
		}

		return next;
	}

	private static int getUpdateAct(int[][] act, char[][] grid, int sizeH, int sizeW, int h, int w) {
		if ((h == (sizeH - 1)) && (w == (sizeW - 1))) {
			return act[h][w] + 1;
		}
		else if (grid[h][w] == '#') {
			return -1;
		}

		int max = act[h][w];
		if ((h - 1) >= 0) {
			max = Math.max(max, act[h - 1][w]);
		}
		if ((h + 1) < sizeH) {
			max = Math.max(max, act[h + 1][w]);
		}
		if ((w - 1) >= 0) {
			max = Math.max(max, act[h][w - 1]);
		}
		if ((w + 1) < sizeW) {
			max = Math.max(max, act[h][w + 1]);
		}

		return max;
	}
}