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 <iostream>
#include <queue>
using namespace std;

const int MAXN = 55;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
char mp[MAXN][MAXN];
bool se[MAXN][MAXN];
int n, m, dis[MAXN][MAXN];
queue<pair<int, int> > Q;

bool isval(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m && mp[x][y] == '.';
}

void BFS(pair<int, int> a) {
	for (int k = 0; k < 4; k++) {
		int x = a.first + dx[k], y = a.second + dy[k];
		if (isval(x, y) && !se[x][y]) {
			se[x][y] = 1;
			Q.push({ x, y });
			dis[x][y] = dis[a.first][a.second] + 1;
		}
	}
}

int main() {
	cin >> n >> m;
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> mp[i][j], cnt += mp[i][j] == '#';
	dis[n - 1][m - 1] = -1;
	Q.push({ 0, 0 });
	se[0][0] = 1;
	dis[0][0] = 1;
	while (!Q.empty())
		BFS(Q.front()), Q.pop();
	if (dis[n - 1][m - 1] == -1)
		return cout << -1, 0;
	cout << n * m - cnt - dis[n - 1][m - 1];
}