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 PYTHON):

Solution:
import sys
import copy
from collections import deque
import time
from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def bfs(board, H, W):
    is_visit = [[False for j in range(W)] for i in range(H)]
    move_list = [(1,0),(-1,0),(0,1),(0,-1)]
    now_pos_list = deque([((0, 0), 1)])
    while 1:
        if len(now_pos_list) <= 0:
            return -1;

        pos = now_pos_list.popleft()
        if pos[0][0] == H -1 and pos[0][1] == W -1:
            return pos[1]

        for move in move_list:
            new_y = pos[0][0] + move[0]
            new_x = pos[0][1] + move[1]
            if new_x >= 0 and new_y >= 0 and  new_x < W and new_y < H:
                if board[new_y][new_x] == "." and is_visit[new_y][new_x] == False:
                    is_visit[new_y][new_x] = True
                    now_pos_list.append(((new_y, new_x), pos[1] + 1))


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    board =[]
    for i in range(H):
        input_raw = read_func().strip()
        board.append(input_raw)
    black_num = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black_num += 1

    score = bfs(board, H, W)
    if score < 0:
        print -1
    else:
        print H * W - black_num - score


if __name__ == '__main__':
    main()