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, cnt = 0;
  cin >> h >> w;

  vector<vector<char>> s(h, vector<char>(w));
  for (auto &r : s) {
    for (auto &c : r) {
      cin >> c;
      cnt += c == '#';
    }
  }

  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 && j >= 0 && j < w && costs[i][j] < 0 &&
        s[i][j] != '#') {
      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;
}