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 <cstdio>
#include <queue>
#define N 55
using namespace std;

int n, m, cnt;
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
struct st {
	int r, c, z;
};
queue<st> qu;
char a[N][N];
bool v[N][N];
void f(int p, int q, int w) {
	if (v[p][q] || a[p][q] != '.') return;
	v[p][q] = 1;
	qu.push({p, q, w});
}
int main()
{
	int i, j;
	st t;
	cin >> n >> m;
	for (i = 1; i <= n; i++) {
		scanf ("%s", &a[i][1]);
		for (j = 1; j <= m; j++) if (a[i][j] == '#') cnt++;
	}
	f(1, 1, 1);
	while (!qu.empty()) {
		t = qu.front(); qu.pop();
		if (t.r == n && t.c == m) break;
		for (i = 0; i < 4; i++) {
			f(t.r + dr[i], t.c + dc[i], t.z + 1);
		}
	}
	if (t.r == n && t.c == m) cout << n * m - cnt - t.z;
	else cout << -1;
    return 0;
}