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);
            //入力
            int h = Integer.parseInt(sc.next());
            int w = Integer.parseInt(sc.next());
            int[][] list = new int[h][w];
            int[][] list2 = new int[h][w];
            int bcounter = 0;
            int counter = 1;
            
            for(int i=0; i<h; i++){
            	String a = sc.next();
            	for(int j=0; j<w; j++){
            		list2[i][j] = h*w+1;
            		if(a.substring(j,j+1).equals("#")){
            			list[i][j] = 1;
            			bcounter++;
            		}else{
            			list[i][j] = 0;	
            		}
            	}
            }
            list2[0][0] = 1;
            while(counter != 0){
            	counter = 0;
            	for(int i=0; i<h; i++){
                	for(int j=0; j<w; j++){
                		if(list[i][j] == 0){
                			int a = 1 + Math.min(Math.min(list2[Math.max(0, i-1)][j], list2[Math.min(h-1, i+1)][j]), Math.min(list2[i][Math.max(0, j-1)], list2[i][Math.min(w-1, j+1)]));
                			if(list2[i][j] > a){
                				counter++;
                				list2[i][j] = a;
                			}
                		}
                	}
                }
            }
            
            //出力
            System.out.println(Math.max(-1, h*w - list2[h-1][w-1] - bcounter));
            sc.close();
        }
    }