Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def ceil(a, b): return (a + b - 1) // b

YES = "Yes"
NO = "No"


def check(x, nums):
    x = abs(x)
    dp = [False] * (x + 1)
    dp[0] = True
    for y in nums:
        tmp = [False] * (x + 1)
        for i in range(len(dp)):
            if i + y < len(tmp):
                tmp[i + y] |= dp[i]
            if i - y >= 0:
                tmp[i - y] |= dp[i]
        dp = tmp
    return dp[x]


def solve(s, x, y):
    type_num = [(k, len(list(g))) for k, g in groupby(s)]
    if s[0] == "F":
        x -= type_num[0][1]
        type_num.pop(0)

    h, v = [], []
    now = 0
    for t, n in type_num:
        if t == "F":
            if now == 0:
                h.append(n)
            else:
                v.append(n)
        else:
            if n % 2 != 0:
                now = (now + 1) % 2
    return YES if check(x, h) and check(y, v) else NO


def main():
    s = input()
    x, y = map(int, input().split())

    print(solve(s, x, y))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def ceil(a, b): return (a + b - 1) // b

YES = "Yes"
NO = "No"


def check(x, nums):
    x = abs(x)
    dp = [False] * (x + 1)
    dp[0] = True
    for y in nums:
        tmp = [False] * (x + 1)
        for i in range(len(dp)):
            if i + y < len(tmp):
                tmp[i + y] |= dp[i]
            if i - y >= 0:
                tmp[i - y] |= dp[i]
        dp = tmp
    return dp[x]


def solve(s, x, y):
    type_num = [(k, len(list(g))) for k, g in groupby(s)]
    if s[0] == "F":
        x -= type_num[0][1]
        type_num.pop(0)

    h, v = [], []
    now = 0
    for t, n in type_num:
        if t == "F":
            if now == 0:
                h.append(n)
            else:
                v.append(n)
        else:
            if n % 2 != 0:
                now = (now + 1) % 2
    return YES if check(x, h) and check(y, v) else NO


def main():
    s = input()
    x, y = map(int, input().split())

    print(solve(s, x, y))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(0,n+1):
    for j in range(0,n-i+1):
        bb=n-(i*r+j*g)
        s=bb+i*r+j*g
        if bb<0:
            continue
        if s==n and bb%b==0:
            cnt+=1
        if j*g>n or i*r>n or s-bb>n:break
    if i*r>n:break
print(cnt)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(0,n+1):
    for j in range(0,n-i+1):
        bb=n-(i*r+j*g)
        s=bb+i*r+j*g
        if bb<0:
            continue
        if s==n and bb%b==0:
            cnt+=1
        if j*g>n or i*r>n or s-bb>n:break
    if i*r>n:break
print(cnt)
### BUGGY CODE ###

N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*N ]

mod = 1000000007

def gcd(x,y):
    if y==0:return x
    return gcd(y,x%y)

c = {}
n0 = 0
for a,b in AB:
    if a==b==0:
        n0 += 1
    elif a==0:
        c[(0,1)] = c.get((0,1),0) +1
    elif b==0:
        c[(1,0)] = c.get((1,0),0) +1
    else:
        g = gcd(a,b)
        a,b = a//g,b//g
        if a<0:
            a *= -1
            b *= -1
        c[(a,b)] = c.get((a,b),0) +1

ans = 1
done = set()
for k,n in c.items():
    if k in done: continue
    a,b = k
    if b>0:
        an,bn = b,-a
    else:
        an,bn = -b,a
    m = c.get((an,bn),0)
    ans *= (pow(2,n,mod) + pow(2,m,mod) - 1)%mod
    ans %= mod
    done.add((a,b))
    done.add((an,bn))

ans = ans -1 +n0
ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*N ]

mod = 1000000007

def gcd(x,y):
    if y==0:return x
    return gcd(y,x%y)

c = {}
n0 = 0
for a,b in AB:
    if a==b==0:
        n0 += 1
    elif a==0:
        c[(0,1)] = c.get((0,1),0) +1
    elif b==0:
        c[(1,0)] = c.get((1,0),0) +1
    else:
        g = gcd(a,b)
        a,b = a//g,b//g
        if a<0:
            a *= -1
            b *= -1
        c[(a,b)] = c.get((a,b),0) +1

ans = 1
done = set()
for k,n in c.items():
    if k in done: continue
    a,b = k
    if b>0:
        an,bn = b,-a
    else:
        an,bn = -b,a
    m = c.get((an,bn),0)
    ans *= (pow(2,n,mod) + pow(2,m,mod) - 1)%mod
    ans %= mod
    done.add((a,b))
    done.add((an,bn))

ans = ans -1 +n0
ans %= mod
print(ans)
### BUGGY CODE ###

from itertools import permutations
class Solve():
    def __init__(self):
        self.N, self.M, self.R = map(int, input().split())
        self.r = list(map(int, input().split()))
        self.route = [[float('inf') for _ in range(self.N)] for _ in range(self.N)]
        for _ in range(self.M):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        for i in range(self.N):
            self.route[i][i] = 0

    def WarshallFloid(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if self.route[i][j] > self.route[i][k] + self.route[k][j]:
                        self.route[i][j] = self.route[i][k] + self.route[k][j]

    def execute(self):
        self.WarshallFloid()
        ans = float('inf')
        checked = set()
        for path in permutations(self.r):
            if tuple(reversed(path)) in checked:
                continue
            checked.add(tuple(reversed(path)))
            temp = 0
            for i in range(self.R - 1):
                temp += self.route[path[i] - 1][path[i + 1] - 1]
            ans = min(ans, temp)
        print(ans)


if __name__ == '__main__':
    Solve().execute()

### FIXED CODE ###

from itertools import permutations
class Solve():
    def __init__(self):
        self.N, self.M, self.R = map(int, input().split())
        self.r = list(map(int, input().split()))
        self.route = [[float('inf') for _ in range(self.N)] for _ in range(self.N)]
        for _ in range(self.M):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        for i in range(self.N):
            self.route[i][i] = 0

    def WarshallFloid(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if self.route[i][j] > self.route[i][k] + self.route[k][j]:
                        self.route[i][j] = self.route[i][k] + self.route[k][j]

    def execute(self):
        self.WarshallFloid()
        ans = float('inf')
        checked = set()
        for path in permutations(self.r):
            if tuple(reversed(path)) in checked:
                continue
            checked.add(tuple(reversed(path)))
            temp = 0
            for i in range(self.R - 1):
                temp += self.route[path[i] - 1][path[i + 1] - 1]
            ans = min(ans, temp)
        print(ans)


if __name__ == '__main__':
    Solve().execute()
### BUGGY CODE ###

n = int(input())
a_li = list(map(int, input().split()))

ans = 1
for a in a_li:
    ans *= a

if ans > 1000000000000000000:
    print(-1)
    exit()
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a_li = list(map(int, input().split()))

if 0 in a_li:
    print(0)
    exit()

ans = 1
a_li = [a for a in a_li if a != 1 and a != 0]
a_li.append(1)
for a in a_li:
    ans *= a
    if ans > 1000000000000000000:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    [(input_hp.sort(reverse=True) ,input_hp.pop(i)) for i in range(input_line[1])]
    print(sum(input_hp))

### FIXED CODE ###

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    input_hp.sort()
    result_input_hp = len(input_hp) - input_line[1]
    sum_total = sum(input_hp[:result_input_hp])
    print(sum_total)
### BUGGY CODE ###

# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

# Implementation
class ModInt:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
    
    def __add__(self, o):
        return ModInt((self.n + o.n) % self.MOD, self.MOD)

    def __sub__(self, o):
        return ModInt((self.n - o.n + self.MOD) % self.MOD, self.MOD)

    def __mul__(self, o):
        return ModInt((self.n * o.n) % self.MOD, self.MOD)

    def __iadd__(self, o):
        self.n = (self.n + o.n) % self.MOD
        return self

    def __isub__(self, o):
        self.n = (self.n - o.n + self.MOD) % self.MOD
        return self

    def __imul__(self, o):
        self.n = (self.n * o.n) % self.MOD
        return self

    def __str__(self): return str(self.n)

MOD = 998244353
N, S = read_tupple()
A = read_array()

dp = [[ModInt(0, MOD) for j in range(S+1)] for i in range(N+1)]
dp[0][0] = ModInt(1, MOD)
for i in range(N):
    for j in range(S+1):
        dp[i + 1][j] += ModInt(2, MOD) * dp[i][j]
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
print(dp[N][S])

### FIXED CODE ###

# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

# Implementation
# class ModInt:
#     def __init__(self, n, MOD):
#         self.n = n
#         self.MOD = MOD
    
#     def __add__(self, o):
#         return ModInt((self.n + o.n) % self.MOD, self.MOD)

#     def __sub__(self, o):
#         return ModInt((self.n - o.n + self.MOD) % self.MOD, self.MOD)

#     def __mul__(self, o):
#         return ModInt((self.n * o.n) % self.MOD, self.MOD)

#     def __iadd__(self, o):
#         self.n = (self.n + o.n) % self.MOD
#         return self

#     def __isub__(self, o):
#         self.n = (self.n - o.n + self.MOD) % self.MOD
#         return self

#     def __imul__(self, o):
#         self.n = (self.n * o.n) % self.MOD
#         return self

#     def __str__(self): return str(self.n)

MOD = 998244353
N, S = read_tupple()
A = read_array()

dp = [[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i + 1][j] = (dp[i + 1][j] + 2 * dp[i][j]) % MOD
        if j - A[i] >= 0:
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - A[i]]) % MOD
print(dp[N][S])
### BUGGY CODE ###

n, m = map(int, input().split())
s = [int(input()) for _ in range(m)]
s.append(n + 1)

dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n + 1):
    if i not in s:
        dp[i] += dp[i - 1]
        if i > 1:
            dp[i] += dp[i - 2]
            dp[i] = dp[i] % (10 ** 9 + 7)

print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
s = [int(input()) for _ in range(m)]
s.append(n+1)

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1

for i in range(n - 1):
    dp[i + 2] = dp[i + 1] + dp[i]
mae = 0
ans = 1
for i in s:
    if i == mae:
        ans=0
    else:
        ans *= dp[i - 1 - mae]

    mae = i + 1
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

# ABC117c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
sa = [0]
for i in range(1, m):
    sa.append(x[i]-x[i-1])
# print(x)
# print(sa)
# print('aa')

for _ in range(min(n-1, len(sa)-1)):
    sa.remove(max(sa))
# print(sa)
print(sum(sa))

### FIXED CODE ###

def main():
    # ABC117c
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    if(m == 1):
        print(0)
        exit(0)
    if(n >= m):
        print(0)
        exit(0)
    x.sort()
    sa = [0]
    for i in range(1, m):
        sa.append(x[i]-x[i-1])
    # print(x)
    # print(sa)
    # print('aa')
    sa.sort()
    # or _ in range(min(n-1, len(sa)-1)):
    #    sa = sa[:-1]
    # print(sa)
    print(sum(sa[:len(sa)-min(n-1, len(sa)-1)]))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

lim = v[0]+1
for i in range(1, N):
  lim += v[i]
  for val in range(1, lim):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break


### FIXED CODE ###

N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

lim = v[0]+1
for i in range(1, N):
  lim += v[i]
  for val in range(1, lim):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力

if __name__ == "__main__":
    
    N = int(input())
    INPUT = list(map(int, input().split()))

    output = 1
    for i in INPUT:
        output = output * i

    if output > 10 ** 18:
        output = -1

    print(output)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力

if __name__ == "__main__":
    
    N = int(input())
    INPUT = list(map(int, input().split()))


    if 0 in INPUT:
        output = 0
    else:
        output = 1
        for i in INPUT:
            output = output * i
            
            if output > 10 ** 18:
                output = -1
                break

    print(output)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]

array = []
for i in range(N):
    a, b = [int(x) for x in input().split()]
    array.extend([a for x in range(b)])

array.sort()
print(array[K-1])


### FIXED CODE ###

N, K = [int(x) for x in input().split()]

array = []
count = 0
for i in range(N):
    array.append(tuple(map(int, input().split())))

array.sort()
K -= 1
for tup in array:
    if K < tup[1]:
        print(tup[0])
        break
    else:
        K -= tup[1]
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():

    Q = int(input())
    ma = 10 ** 5 + 1
    dp = [0] * ma
    dp[2] = 1

    for i in range(3,ma,2):
        if dp[i] == 0:
            dp[i] = 1
            if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
                dp[i] = 2
            for j in range(i * 2,ma,i):
                dp[j] = 3

    for _ in range(Q):
        l,r = map(int,input().split())
        print(dp[l:r+1].count(2))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():

    Q = int(input())
    ma = 10 ** 5 + 1
    dp = [0] * ma
    dp[2] = 1

    for i in range(3,ma,2):
        if dp[i] == 0:
            dp[i] = 1
            if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
                dp[i] = 2
            for j in range(i * 2,ma,i):
                dp[j] = 3

    ruiseki = [0] * ma

    for i in range(1,ma):
        if dp[i] == 2:
            ruiseki[i] = ruiseki[i-1] + 1
        else:
            ruiseki[i] = ruiseki[i-1]

    for _ in range(Q):
        l,r = map(int,input().split())
        print(ruiseki[r] - ruiseki[l-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
n=input()
a=map(int, raw_input().split())
a.sort()
a.reverse()

def comb(N,R):
	return math.factorial(N)/( math.factorial(N-R)*math.factorial(R) )

c=a[0]

b=[0 for i in range(n)]
for i in range(1,n):
	b[i]=abs(a[i]-c/2)

min_b=min(b[1:])

d=[]
for i in range(1,n):
	if b[i]==min_b:
		d.append( (comb(c,a[i]),a[i]) )

print c,sorted(d, key=lambda x:x[0],reverse=True)[0][1]


### FIXED CODE ###

import math
n=input()
a=map(int, raw_input().split())
a.sort()
a.reverse()


c=a[0]

b=[0 for i in range(n)]
for i in range(1,n):
	b[i]=abs(a[i]-c/2)

min_b=min(b[1:])

d=[]
for i in range(1,n):
	if b[i]==min_b:
		d.append(a[i])

d.sort()
d.reverse()

print c,d[0]
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, n))
# 小さすぎても怒られるので
 
cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)
 
toru = [0] * (n+1)
def dfs(ns, prev, now, toru):
    end = defaultdict(int)
    k = cs[now]
    end[k] = 1
    s = 1 # nowで終わるパスの種類
    for u in ns[now]:
        if u==prev:
            continue
        tmp_end, tmp_toru, tmp_s = dfs(ns, now, u, toru)
        # toruの更新
        for kk, vv in tmp_end.items():
            if kk not in end:
                toru[kk] += vv * s
            else:
                toru[kk] += vv * s + end[kk] * (tmp_s+1) - ((vv+1) * end[kk])
        for kk, vv in end.items():
            if kk not in tmp_end:
                toru[kk] += vv * tmp_s
        # end, sの更新
        end[k] += tmp_s
        for kk,vv in tmp_end.items():
            if k!=kk:
                end[kk] += tmp_end[kk]
        s += tmp_s
    toru[k] += 1
#     print(now, prev, end, toru, s)
    return end, toru, s
end, toru, s = dfs(ns, prev=-1, now=1, toru=toru)
 
for item in toru[1:]:
    print(item)

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
inf=10**10

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        p=[]    
        if v>W-1: p.append(v-W)
        if v+W<H*W: p.append(v+W)
        if v%W>0: p.append(v-1)
        if v%W<W-1: p.append(v+1)
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def f(s):
    r=[]
    for j in range(W):
        if s[j]=="#": r.append(inf)
        elif s[j]==".": r.append(0)
    return r

H,W=map(int,input().split())
x=[f(input()) for i in range(H)]

cost = [[float("inf") for i in range(H*W)] for i in range(H*W)] 
for i in range(H*W):
    for j in range(H*W):
        if x[i//W][i%W]==inf or x[j//W][j%W]==inf: continue
        if abs(i-j)==W: cost[i][j],cost[j][i]=1,1
        elif i-j==1 and i%W!=0: cost[i][j],cost[j][i]=1,1
        elif j-i==1 and j%W!=0: cost[i][j],cost[j][i]=1,1

ans=0
for i in range(H):
    for j in range(W):
        if x[i][j]==0: ans+=1

ans-=dijkstra(0,H*W,cost)[H*W-1]+1
print(ans if ans>=0 else -1)

### FIXED CODE ###

import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
        return -1

    except RuntimeError:
        print(-1)
        sys.exit()


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print( p if p==-1 else ans-p-1)
### BUGGY CODE ###

X = int(input())

def bfs():
    from collections import deque
    queue = deque([0])
    while queue:
        sum_x = queue.popleft()
        if sum_x == X:
            return 1
        if sum_x > X:
            continue

        queue.append(sum_x + 100)
        queue.append(sum_x + 101)
        queue.append(sum_x + 102)
        queue.append(sum_x + 103)
        queue.append(sum_x + 104)
        queue.append(sum_x + 105)
    return 0

ans = bfs()
print(ans)

### FIXED CODE ###

X = int(input())
X_MOD = X % 100
X_DIV = X // 100

import sys
sys.setrecursionlimit(2000)
def dfs(sum_x, cnt_x, num):
    if cnt_x > X_DIV:
        return False
    if sum_x == X_MOD:
        return True

    if num == 1:
        return dfs(sum_x+1, cnt_x+1, 1) or dfs(sum_x+1, cnt_x+2, 2) or dfs(sum_x+3, cnt_x+1, 3) or dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 2:
        return dfs(sum_x+1, cnt_x+2, 2) or dfs(sum_x+3, cnt_x+1, 3) or dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 3:
        return dfs(sum_x+3, cnt_x+1, 3) or dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 4:
        return dfs(sum_x+4, cnt_x+1, 4) or dfs(sum_x+5, cnt_x+1, 5)
    if num == 5:
        return dfs(sum_x+5, cnt_x+1, 5)
    

ans = int(dfs(0,0,1))
print(ans)