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.Scanner;

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());
    
    boolean s[][] = new boolean[H][W];
    int min[][] = new int[H][W];
    int black = 0;
    for (int i = 0; i < H; i++) {
      String str = sc.next();
      for (int j = 0; j < W; j++) {
        char input = str.charAt(j);
        if (input == '#') {
          black++;
          s[i][j] = false;
          min[i][j] = -1;
        } else {
          s[i][j] = true;
          min[i][j] = H * W;
        }
      }
    }
    min[0][0] = 1;
    boolean flag = true;
    while (flag) {
      flag = false;
      for (int i = 0; i < H; i++) {
        for (int j = 0; j < W - 1; j++) {
          if (s[i][j] && s[i][j + 1] && min[i][j] + 1 < min[i][j + 1]) {
            min[i][j + 1] = min[i][j] + 1;
            flag = true;
          }
        }
      }
      for (int j = 0; j < W; j++) {
        for (int i = 0; i < H - 1; i++) {
          if (s[i][j] && s[i + 1][j] && min[i][j] + 1 < min[i + 1][j]) {
            min[i + 1][j] = min[i][j] + 1;
            flag = true;
          }
        }
      }
      for (int i = 0; i < H; i++) {
        for (int j = W - 1; j > 0; j--) {
          if (s[i][j] && s[i][j - 1] && min[i][j] + 1 < min[i][j - 1]) {
            min[i][j - 1] = min[i][j] + 1;
            flag = true;
          }
        }
      }
      for (int j = 0; j < W; j++) {
        for (int i = H - 1; i > 0; i--) {
          if (s[i][j] && s[i - 1][j] && min[i][j] + 1 < min[i - 1][j]) {
            min[i - 1][j] = min[i][j] + 1;
            flag = true;
          }
        }
      }
    }
    
    if (min[H - 1][W - 1] == H * W) {
      System.out.println(-1);
    } else {
      System.out.println(H * W - black - min[H - 1][W - 1]);
    }
  }
}