import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
dxdy = ((-1,0), (1,0), (0,-1), (0,1))
H, W = map(int,input().split())
maze = []
visited = [ [0]*W for _ in range(H)]
black = 0
for h in range(H):
    s = input()
    maze.append(s)
    for c in s:
        if c=='#':
            black += 1
q = queue.Queue()
q.put((0,0,0))
cost = -1
while(not q.empty()):
    y, x, d = q.get()
    if x == W-1 and y == H-1:
        cost = d
        break
    if visited[y][x] == 1:
        continue
    else:
        visited[y][x] = 1
        for dx, dy in  dxdy:
            if (0<= x+dx < W) and (0<= y+dy < H):                
                if visited[y+dy][x+dx] == 0 and maze[y+dy][x+dx]=='.':
                    q.put((y+dy,x+dx,d+1))
if cost==-1:
    print (-1)
else:
    print (H*W-cost-1-black)

import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利
R, C = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())
maze = []
visited = [ [0]*C for _ in range(R)]
for r in range(R):
    s = input()
    maze.append(s) # 二次元リストにせず、文字列のリストのままでOK
q = queue.Queue()
q.put((sy-1,sx-1,0)) # スタート地点をenqueue
while(not q.empty()):
    y, x, d = q.get()
    if x == gx-1 and y == gy-1: # ゴールにたどり着いたら終了
        ans = d
        break
    if visited[y][x] == 1: # 訪問済みの場合は無視する
        continue
    else:
        visited[y][x] = 1 # 訪問フラグを立てる
        for dx, dy in  dxdy:
            if (0<= x+dx < C) and (0<= y+dy < R): # 範囲内に収まっているか               
                if visited[y+dy][x+dx] == 0 and maze[y+dy][x+dx]=='.': # 見訪問かつ通行可能か
                    q.put((y+dy,x+dx,d+1)) # 距離を+1してenqueue
print (ans)

input = sys.stdin.readline

sys.setrecursionlimit(int(1E+7))

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N+1)]
    for n in range(N-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    V = [0] * (N+1)
    for q in range(Q):
        p, x = map(int, input().split())
        V[p] += x # `操作`の際の根に当たるノードのカウンター`V`に先に値を加算する。

    def dfs(i, parent, acc): # 深さ優先探索
        V[i] += acc # 親ノードまでの累積値を加算
        for j in link[i]:
            if j != parent: # 親ノードを追加しない
                dfs(j,i,V[i])
    cur = 1
    parent = 0
    acc = 0
    dfs(cur, parent , acc) # 親ノードを0としてスタート
    V = [str(v) for v in V]
    print (" ".join(V[1:]))

if __name__ == '__main__':
    main()

for comb in combinations(range(3),2):
    print (comb)

(0, 1)
(0, 2)
(1, 2)

from itertools import combinations
N, M = map(int, input().split())
link = [[0 for i in range(N)] for j in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    link[x-1][y-1] = 1
    link[y-1][x-1] = 1

ans = 1
for i in range(N,1,-1): # N, N-1, N-2, ... 2
    for comb in combinations(range(N),i):

for c in combinations(comb, 2): # 議員の集合に対して考えられるペアを列挙
    if (link[c[0]][c[1]] == 0): # 一つでも知り合いでない組があればNG
        break
else: # 派閥が作れた段階でプログラムを終了
    print (i)
    exit()

from itertools import combinations
N, M = map(int, input().split())
link = [[0 for i in range(N)] for j in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    link[x-1][y-1] = 1
    link[y-1][x-1] = 1

for i in range(N,1,-1): # N, N-1, N-2, ... 2
    for comb in combinations(range(N),i):
        for c in combinations(comb, 2): # 議員の集合に対して考えられるペアを列挙
            if (link[c[0]][c[1]] == 0): # 一つでも知り合いでない組があればNG
                break
        else: # 派閥が作れた段階でプログラムを終了
            print (i)
            exit()
print (1)

N = input()
if '7' in N:
    print ('Yes')
else:
    print ('No')

N = int(input())
ans = 0
for n in range(1,N+1):
    if (n%3 != 0 and n%5 != 0):
        ans += n
print (ans)

from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        gcd_ij = gcd(i, j)
        for k in range(1,K+1):
            ans += gcd(gcd_ij, k)
print (ans)

N = int(input())
S = input()
ans = S.count('R') * S.count('G') * S.count('B') # 一つ目の条件

for i in range(N):
    for j in range(1,N): # 1から
        if (i-j<0 or i+j>=N): # リストの範囲内かを確認
            break
        l = S[i-j]
        m = S[i]
        r = S[i+j]
        if l!=m and m!=r and r!=l: # 二つ目の条件
            ans -= 1
print (ans)

MOD = int(1e+9 + 7) # 忘れずにintをつける
N, K = map(int, input().split())
 
cnt = [0] * (K + 1) # 後々のことを考え、サイズをK+1にする
　               
for x in range(1, K + 1): # 先頭0は使わない
    cnt[x] = pow(K // x, N, MOD) # 要素が全てXの倍数となるような数列の個数をXごとに求める
 
for x in range(K, 0, -1): # 大きい順に計算
    for i in range(2, K // x + 1): # 2X, 3Xの個数を求めてひく
        cnt[x] -= cnt[x * i]

ans = 0
for k in range(K+1):
    ans += cnt[k] * k # gcdがkである組はA[k]個ある
ans = ans % MOD # ここでもMODをつける
print(ans)

MOD = int(1e+9 + 7) # 忘れずにintをつける
N, K = map(int, input().split())
 
cnt = [0] * (K + 1) # 後々のことを考え、サイズをK+1にする
　               
for x in range(1, K + 1): # 先頭0は使わない
    cnt[x] = pow(K // x, N, MOD) # 要素が全てXの倍数となるような数列の個数をXごとに求める
print (cnt)

for x in range(K, 0, -1): # 大きい順に計算
    for i in range(2, K // x + 1): # 2X, 3Xの個数を求めてひく
        cnt[x] -= cnt[x * i]
print (cnt)

ans = 0
for k in range(K+1):
    ans += cnt[k] * k # gcdがkである組はA[k]個ある
ans = ans % MOD # ここでもMODをつける
print(ans)

import bisect
A = [2, 3, 5, 7, 11]
x = 4
ins = bisect.bisect(A, x)
print (ins)

2

A.insert(ins, x)
print (A)

[2, 3, 4, 5, 7, 11]

A = [2, 3, 5, 7, 11]
x = 5
print (bisect.bisect(A, x))

4

print (bisect.bisect(A, x))
print (bisect.bisect_left(A, x))
print (bisect.bisect_right(A, x))

4
3
4

B = [2, 2, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11]

L = 3
U = 7
print (bisect.bisect_right(B, U) - bisect.bisect_left(B, L))

import bisect
import unittest

def meguru_bisect(ng, ok, func):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def bisect_left(a, x):
    def func(i):
        return x <= a[i]
    return meguru_bisect(-1, len(a), func)

def bisect_right(a, x):
    def func(i):
        return x < a[i]
    return meguru_bisect(-1, len(a), func)

class TestBisect(unittest.TestCase):
    def test_bisect(self):
        test_patterns = [
            ([2,3,4,4,5,6], 6),
            ([], 6),
            ([3,3], 0),
            ([3,3], 6),
        ]
        for a, x in test_patterns:
            with self.subTest(a=a, x=x):
                self.assertEqual(bisect_left(a, x), bisect.bisect_left(a, x))
            with self.subTest(a=a, x=x):
                self.assertEqual(bisect_right(a, x), bisect.bisect_right(a, x))


if __name__=='__main__':
    a = [2,3,4,4,5,6]
    x = 6
    print (bisect_left(a, x))
    print (bisect.bisect_left(a, x))
    print (bisect_right(a, x))
    print (bisect.bisect_right(a, x))

def is_ok(x):
    ls = []
    for i in range(N):
        ls.append((x-H[i])//S[i]) # いつまでに割れば良いか
    ls.sort() # 期限が近いものから先にわる
    for n in range(N):
        if (ls[n] < n): 
            return False # 時間ぎれ
    return True

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

N = int(input())
H = []
S = []
for i in range(N):
    h, s = map(int,input().split())
    H.append(h)
    S.append(s)
print (meguru_bisect(0,int(1e+14)))

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for b in B:
    a = bisect.bisect_left(A, b) # 挿入点はどの同じ値よりも左
    c = bisect.bisect_right(C, b) # 挿入点はどの同じ値よりも右
    ans += a * (len(C)-c)
print (ans)

import unittest

def some_func():
    raise ValueError

class TestMethods(unittest.TestCase):
    def test_assert_raises(self):
        with self.assertRaises(ValueError):
            some_func()

if __name__ == '__main__':
    unittest.main()

import unittest

def some_func():
    raise ArithmeticError

class TestMethods(unittest.TestCase):
    def test_assert_raises(self):
        with self.assertRaises(ValueError):
            some_func()

if __name__ == '__main__':
    unittest.main()

class TestMethods(unittest.TestCase):
    def test_assert_raises(self):
        self.assertRaises(ValueError, some_func)