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 JAVA):

Solution:
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int h=sc.nextInt();
        int w=sc.nextInt();
        String s;
        int white=0;
        boolean[][]input=new boolean[h][w];
        boolean[][]visited=new boolean[h][w];
        visited[0][0]=true;
        for(int i=0;i<h;i++){
            s=sc.next();
            for(int j=0;j<w;j++){
                if(s.charAt(j)=='.'){
                    input[i][j]=true;
                    white++;
                }
                
            }
        }
        int[] movex={1,0,-1,0};
        int[] movey={0,1,0,-1};
        Queue<Integer> queuex=new ArrayDeque<>();
        Queue<Integer> queuey=new ArrayDeque<>();
        queuex.add(0);
        queuey.add(0);
        int size;
        for(int i=0;i<h*w;i++){
            size=queuex.size();
            for(int j=0;j<size;j++){
                for(int k=0;k<4;k++){
                    try{
                        if(input[queuex.peek()+movex[k]][queuey.peek()+movey[k]]&&!visited[queuex.peek()+movex[k]][queuey.peek()+movey[k]]){
                            visited[queuex.peek()+movex[k]][queuey.peek()+movey[k]]=true;
                            queuex.add(queuex.peek()+movex[k]);
                            queuey.add(queuey.peek()+movey[k]);
                            
                        }
                        if(queuex.peek()+movex[k]==h-1&&queuey.peek()+movey[k]==w-1){
                            System.out.println(white-i-2);
                            return;
                        }
                    }catch(Exception e){}
                }
                queuex.poll();
                queuey.poll();
            }
        }
        System.out.println(-1);
    }
}