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

public class Main {
    private static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public void main(Scanner sc) {
        int h = sc.nextInt();
        int w = sc.nextInt();
        int map[][] = new int[h][w];
        int white = 0;
        for (int i = 0; i < h; i++) {
            String str = sc.next();
            for (int j = 0; j < w; j++) {
                if (str.charAt(j) == '#') {
                    map[i][j] = -1;
                } else {
                    white++;
                }
            }
        }

        int minTern = solveMaze(h, w, map);
        System.out.println(minTern != -1 ? white - minTern : minTern);
    }

    private int solveMaze(int h, int w, int map[][]) {
        int dx[] = { 1, 0, -1, 0 };
        int dy[] = { 0, 1, 0, -1 };
        Queue<Point> queue = new ArrayDeque<>();

        map[0][0] = 1;
        queue.add(new Point(0, 0));

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            int now = map[p.y][p.x];
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || nx >= w || ny < 0 || ny >= h || map[ny][nx] != 0) {
                    continue;
                }

                map[ny][nx] = now + 1;
                if ((nx == w - 1) && (ny == h - 1)) {
                    queue.clear();
                    return map[ny][nx];
                }
                queue.add(new Point(nx, ny));
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}