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<cstdio>
#include<cstring>
char s[55][55];
int row,col;
int q[55*55*2],op,cl;
int d[55][55];
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,1,0,-1};
int main(){
	scanf("%d%d",&row,&col);
	int all = 0;
	for(int i=0; i<row; i++){
		scanf("%s",s[i]);
		for(int j=0; j<col; j++)
			if(s[i][j] == '.')
				all ++;
	}
	memset(d,-1,sizeof(d));
	q[op++] = 0;
	q[op++] = 0;
	d[0][0] = 0;
	while(cl<op){
		int x = q[cl++];
		int y = q[cl++];
		for(int k=0; k<4; k++){
			int xx = x+dx[k],yy=y+dy[k];
			if(xx>=0 && xx<row && yy>=0 && yy<col && s[xx][yy] != '#' && d[xx][yy] == -1){
				d[xx][yy] = d[x][y] + 1;
				q[op++] = xx;
				q[op++] = yy;
			}
		}
	}
	if(d[row-1][col-1] == -1)puts("-1");else
	printf("%d\n",all-d[row-1][col-1]-1);
	return 0;
}