Cave Advanture

Start from the top-left corner (0,0) of the grid and reach the bottom-right corner. ! is a passable cell and x is an obstacle. Each step moves exactly one cell left, right, or down; you cannot move up or re-enter a visited cell. Find the maximum number of cells on a path that reaches the exit (counting both the start and the end); output −1 if the exit cannot be reached.

输入格式

This site's input: the first line contains R C (1..200), followed by R strings of length C containing only ! and x; the entrance or exit may also be blocked.

输出格式

Output the maximum number of visited cells, or −1.

样例 1

输入：

3 3
!!!
!!!
!!!

输出：

9

样例 2

输入：

2 2
!x
x!

输出：

-1

样例 3

输入：

1 1
!

输出：

1

样例说明

Example 1: in an empty 3×3 grid you can snake row by row through all 9 cells and finish at the bottom-right corner.

Example 2: the cells to the right of and below the entrance are both obstacles, so the exit cannot be reached; the output is −1.

Example 3: the start is also the end and is passable, so the number of visited cells is 1.