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;
char a[55][55];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool v[55][55];
struct s{
    int x,y,d;
};
int main() {
int n,m;
cin>>n>>m;
int bl=0;
for(int i=0;i<n;i++)
{cin>>a[i];
for(int j=0;j<m;j++)
{
if(a[i][j]=='.')
bl++;
}
}
queue
 q;
s s1;
s1.x=0;
s1.y=0;
s1.d=1;
q.push(s1);
int w=0;
while(!q.empty())
{
s t=q.front();
q.pop();
v[t.x][t.y]=1;

if(t.x==n-1&&t.y==m-1)
{

    w=t.d;
    break;
}
for(int i=0;i<4;i++)
{
    int nx=dx[i]+t.x;
    int ny=dy[i]+t.y;
    if(nx<0||nx>=n||ny<0||ny>=m||v[nx][ny]||a[nx][ny]=='#')
    continue;
    s t1;
    v[nx][ny]=1;
    t1.x=nx;
    t1.y=ny;
    t1.d=t.d+1;
    q.push(t1);
}
}
int ans=bl-w;
if(w!=0)
cout<<ans;
else cout<<-1;
    return 0;
}