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;
int H,W;
char board[50][50];
int white;
struct P {int h,w,d;};
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
 
 
int bfs(){
	queue<P> Q;
  	Q.push(P{0,0,0});
    board[0][0]='#';  
  
    while(Q.size()){  
  	P p=Q.front();Q.pop();
    if (p.h==H-1 && p.w==W-1)return p.d;
 	int nh,nw;
  	for(int i=0;i<4;i++){
      nh=p.h+dh[i];nw=p.w+dw[i];
  	  if(0<=nh && nh<H && 0<=nw && nw<W &&  board[nh][nw]=='.'){
        Q.push(P{nh,nw,p.d+1});
 	    board[nh][nw]='#';
      }
    }
    }
    return -1;
}
		
int main(){
	cin >>H >>W;
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      cin >>board[i][j];  
      if(board[i][j]=='.')white++;
    }}
    int dist=bfs();
    int ans;
    ans=(dist==-1)?-1:(white-dist-1); 
    
    
    cout << ans <<endl;
    return 0;
    }