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;
using P = pair<int,int>;

int H,W, d[50][50];
char grid[50][50];

int BFS(void){
	queue<P> Q;	Q.push( {0,0} );
	d[0][0]=1;

	int dy[4]={-1,1,0,0}, dx[4]={0,0,-1,1};

	while(Q.size()){
		P u = Q.front();	Q.pop();
		int y=u.first, x=u.second;

		for(int i=0;i<4;i++){
			int nY=y+dy[i], nX=x+dx[i];
			if(nY<0||nX<0||nY>=H||nX>=W)continue;		// 範囲外
			else if(grid[nY][nX]=='#')continue;			// 白マスじゃない
			else if(d[nY][nX]!=0)continue;				// すでに踏破している

			d[nY][nX]=d[y][x]+1;
			Q.push( {nY,nX} );
		}
	}


	return d[H-1][W-1];
}

int main(){
	cin>>H>>W;

	int whiteSum=0;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin>>grid[i][j];
			if(grid[i][j]=='.')whiteSum++;
		}
	}

	int step=BFS();
	if(step==0){
		cout<<"-1"<<endl;
	}else{
		cout<<whiteSum-step<<endl;
	}
	

	return 0;
}