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;
#define rep(i,n) for(int i=0;i<(n);i++)
#define INF 10000
#define PII pair<int,int>
int H,W;
string S[51];
int A[51][51];
int dh[4]={1,0,-1,0},dw[4]={0,1,0,-1};
int bfs(){
  rep(i,H) rep(j,W) A[i][j]=INF;
  queue<PII> Q;
  Q.push(PII(0,0));
  A[0][0]=1;
  while(Q.size()){
    PII P=Q.front();
    Q.pop();
    if(P.first==H-1&&P.second==W-1) break;
    rep(i,4){
      int nh=P.first+dh[i],nw=P.second+dw[i];
      if(nh>=0&&nh<H&&nw>=0&&nw<W&&S[nh][nw]=='.'&&A[nh][nw]==INF){
        Q.push(PII(nh,nw));
        A[nh][nw]=A[P.first][P.second]+1;
      }
    }
  }
 return A[H-1][W-1];
}
int main(){
  cin>>H>>W;
  rep(i,H) cin>>S[i];
  int s=0;
  rep(i,H) rep(j,W) if(S[i][j]=='.') s++;
  cout<<((bfs()!=INF)?s-bfs():-1)<<endl;
}