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

Solution:
#include        <bits/stdc++.h>
using namespace std;

int     main() {
	int H, W;
	cin >>H >>W;
	vector<vector<int>> s(H+2, vector<int> (W+2, 10000));
	int SS=0;
	for (int i=1; i<=H; i++)
		for (int j=1; j<=W; j++) {
			char C;
			cin >>C;
			if ('.'==C) {
				s.at(i).at(j)=3000;
				SS++;
			}
		}
	s.at(1).at(1)=1;
	while(true) {
		bool found=false;
		for (int i=1; i<=H; i++)
			for (int j=1; j<=W; j++) {
				if (10000!=s.at(i).at(j)) {
					int V=s.at(i).at(j)-1;
					V=min(V, s.at(i-1).at(j));
					V=min(V, s.at(i+1).at(j));
					V=min(V, s.at(i).at(j-1));
					V=min(V, s.at(i).at(j+1));
					if (V+1<s.at(i).at(j)) {
						s.at(i).at(j)=V+1;
						found=true;
					}
				}
			}
		if (!found)
			break;
	}
	if (3000==s.at(H).at(W)) {
		cout <<-1 <<endl;
	} else {
		cout <<SS-s.at(H).at(W) <<endl;
	}
	return 0;
};