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>
#define MOD (long long)(1e9+7)
using namespace std;
int h,w,vis[55][55],dir[][2]={{0,1},{1,0},{0,-1},{-1,0}};
string s[55];
struct p{
	int x,y,dis;
	p(int a,int b,int c):x(a),y(b),dis(c){};
};
int main()
{
	int ans=-1,bl=0;
	cin >> h >> w;
	for(int i=0; i<h; i++)
	{
		cin >> s[i];
		for(int j=0; j<w; j++) bl+=(s[i][j]=='#'); 
	}
	
	queue<p> q; q.push(p(0,0,1)); vis[0][0]=1;
	while(!q.empty())
	{
		p u=q.front(); q.pop();
		if(s[u.x][u.y] == '#') continue;
		if(u.x == h-1 && u.y == w-1)
		{
			ans=u.dis;
			break;
		}
		for(int i=0; i<4; i++)
		{
			int a=u.x+dir[i][0],b=u.y+dir[i][1];
			if(a>=0 && a<h && b>=0 && b<w && s[a][b]!='#' && !vis[a][b])
			{
				q.push(p(a,b,u.dis+1));
				vis[a][b]=1;
			}
		}
	}
	if(ans==-1) cout << -1;
	else cout << h*w-bl-ans;
	return 0;
}