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 Point{
    int x; int y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        char[][] maze = new char[h][w];
        int vacant = 0;
        for(int i=0;i<h;i++){
            maze[i] = sc.next().toCharArray();
            for(int j=0;j<w;j++){
                if(maze[i][j]=='.'){
                    vacant++;
                }
            }
        }
        sc.close();
        Deque<Point> points = new ArrayDeque<Point>();
        points.addLast(new Point(0,0));
        int[][] distance = new int[h][w];
        for(int i=0;i<h;i++){
            Arrays.fill(distance[i],h*w+1);
        }
        distance[0][0] = 0;
        while(true){
            int x; int y;
            try{
                Point p = points.removeFirst();
                x = p.x; y = p.y;
            }catch(NoSuchElementException e){
                break;
            }
            maze[y][x] = '#';
            if(x==w-1 && y==h-1){
                break;
            }
            int[] dx = {-1,0,1,0}; int[] dy = {0,-1,0,1};
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx==-1 || nx==w || ny==-1 || ny==h || maze[ny][nx]=='#' || distance[ny][nx] != h*w+1){
                    continue;
                }else{
                    points.addLast(new Point(nx,ny));
                    distance[ny][nx] = distance[y][x] + 1;
                }
            }
        }
        if(distance[h-1][w-1] == h*w+1){
            System.out.println(-1);
        }else{
            System.out.println(vacant - distance[h-1][w-1]-1);
        }
    }
}