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.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int black = 0;
        char map[][] = new char[h][w];
        char searchmap[][] = new char[h][w];
        for (int y = 0;y < h;++y){
            String s = sc.next();
            for (int x = 0;x < w;++x){
                map[y][x] = s.charAt(x);
                if(map[y][x] == '#')++black;
                searchmap[y][x] = map[y][x];
            }
        }
        searchmap[0][0] = '!';
        int ser = search(w, h, searchmap);
        if(ser == -1){
            System.out.println(ser);
        }
        else System.out.println((w * h - 1 - ser) - black);
    }

    public static int search(int w,int h,char map[][]){
        int count = 0;
        while (true){
            for (int x = 0;x < w;++x){
                for (int y = 0;y < h;++y){
                    if(map[y][x] == '.'){
                        if(x > 0&&map[y][x - 1] == '!'){
                            map[y][x] = '?';
                        }
                        else if(x < w - 1&&map[y][x + 1] == '!'){
                            map[y][x] = '?';
                        }
                        else if(y > 0&&map[y - 1][x] == '!'){
                            map[y][x] = '?';
                        }
                        else if(y < h - 1&&map[y + 1][x] == '!'){
                            map[y][x] = '?';
                        }
                    }
                }
            }
            if(map[h - 1][w - 1] == '?'){
                return count + 1;
            }
            boolean flag = false;
            for (int y = 0;y < h;++y) {
                for (int x = 0; x < w;++x) {
                    if(map[y][x] == '?'){
                        map[y][x] = '!';
                        flag = true;
                    }
                }
            }
            if(!flag){
                return -1;
            }
            ++count;
        }
    }


}