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:
//幅優先探索　最短でいったぬる
//https://qiita.com/drken/items/996d80bcae64649a6580
import java.util.ArrayList;
import java.util.Scanner;

import java.util.*;
public class Main {
	static int maze[][] ; //短いものを入れておく
	static char c[][];
	static int H;
	static int N;
	static int W;
	static int sy;
	static int sx;
	static int gx;
	static int gy;
	static int dy[] = {0, 1, 0, -1};
	static int dx[] = {1, 0, -1, 0};
	static int box;
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		H = sc.nextInt();
		W = sc.nextInt();
		
		box = 0;
		c = new char[H][W];
		gx = W-1;
		gy = H-1;
		for(int i = 0; i < H; i++) {
			String s = sc.next();
			for(int j = 0; j < W; j++) {
				c[i][j] = s.charAt(j);
				if(s.charAt(j)=='#') {
					
					box++;
				}
			}
		}
		int ans = BFS();
		if(ans == 0 ){
			System.out.println(-1);
		}else {
			System.out.println(H*W - box - ans -1);
		}
	}
	
	public static int BFS() {
		int maze[][] = new int[H][W];
		Queue<Integer> queue_x = new ArrayDeque<>();
		Queue<Integer> queue_y = new ArrayDeque<>();
		
		queue_x.add(sx);
		queue_y.add(sy);
	
		int ans = 0;
		
	
		while(queue_x.size() != 0 && queue_y.size() != 0) {
		//キューの先頭を取り出す。
			int x = queue_x.poll();
			int y = queue_y.poll();
			// a上下左右に移動した場合、どうなるか
			for (int k = 0; k < 4; k++) {
					int xx = x + dx[k];
					int yy = y + dy[k];
					
					if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
								
						if (c[yy][xx]=='.' && maze[yy][xx] == 0) {
								maze[yy][xx] = maze[y][x] + 1;
								queue_x.add(xx);
								queue_y.add(yy);
						}
					}
			}
		}
		return maze[gy][gx];		
	
	}
}