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

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    
    String[] s = sc.nextLine().split(" ");
    int H = Integer.parseInt(s[0]);
    int W = Integer.parseInt(s[1]);
    
    char[][] map = new char[H][W];
    int[][] route = new int[H][W];
    
    int dots = 0;
    for(int i = 0; i < H; i++){
      String str = sc.nextLine();
      for(int j = 0; j < W; j++){
        map[i][j] = str.charAt(j);
        if(i == 0 && j == 0){
          route[i][j] = 1;
          dots++;
        }else if(map[i][j] == '.'){
          route[i][j] = 0;
          dots++;
        }else{
          route[i][j] = -1;
        }
      } 
    }
    
    int[] ih = {+1, 0, -1, 0};
    int[] iw = {0, +1, 0, -1};
    
    Queue<Integer> qh = new ArrayDeque<>();
    Queue<Integer> qw = new ArrayDeque<>();
    qh.add(0);
    qw.add(0);
    boolean b = false;
    
    while(qh.size() > 0){
      int nh = qh.poll();
      int nw = qw.poll();
      
      if(nh == H - 1 && nw == W - 1){
        b = true;
        break;
      }
      
      for(int i = 0; i < 4; i++){
        int fh = nh + ih[i];
        int fw = nw + iw[i];
        
        if(fh >= 0 && fw >= 0 && fh < H && fw < W && route[fh][fw] == 0){
          qh.add(fh);
          qw.add(fw);
          route[fh][fw] = route[nh][nw] + 1;
        }
      }
    }
    if(b){
      System.out.println(dots - route[H-1][W-1]);
    }else{
      System.out.println(-1);
    }
  }
}