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

Solution:
#include <bits/stdc++.h>

using namespace std;

int main(int argc, const char *argv[]) {
  int h, w;
  cin >> h >> w;

  vector<vector<char>> s(h, vector<char>(w));
  int cnt = 0;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cin >> s[i][j];
      if (s[i][j] == '#') {
        cnt++;
      }
    }
  }

  vector<vector<int>> costs(h, vector<int>(w, -1));
  queue<array<int, 3>> q;
  q.push({0, 0, 0});
  while (!q.empty()) {
    auto [i, j, cost] = q.front();
    q.pop();
    if (i < 0 || i > h - 1 || j < 0 || j > w - 1 || costs[i][j] != -1 ||
        s[i][j] == '#') {
      continue;
    }

    costs[i][j] = cost;
    q.push({i - 1, j, cost + 1});
    q.push({i + 1, j, cost + 1});
    q.push({i, j - 1, cost + 1});
    q.push({i, j + 1, cost + 1});
  }

  int cost = costs[h - 1][w - 1];
  if (cost < 0) {
    cout << -1 << '\n';
  } else {
    cout << h * w - (cost + 1) - cnt << '\n';
  }

  return 0;
}