Harryxun/stf_run huggingface dataset:
from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=p-n
                if a in setlst[l]:
                    count+=1
                    Counerlst[l][a]-=1
                    Counerlst[l][n]-=1
                    if Counerlst[l][a]==0:
                        setlst[l].remove(a)
                    if Counerlst[l][n]==0:
                        setlst[l].remove(n)
                    break
print(count)


### FIXED CODE ###

from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=p-n

                if a in setlst[l]:
                    if n==a:
                        if Counerlst[l][n]>=2:
                            count+=1
                            Counerlst[l][n]-=2
                            if Counerlst[l][n]==0:
                                setlst[l].remove(n)
                    else:

                        count+=1
                        Counerlst[l][a]-=1
                        Counerlst[l][n]-=1
                        if Counerlst[l][a]==0:
                            setlst[l].remove(a)
                        if Counerlst[l][n]==0:
                            setlst[l].remove(n)
                    break
print(count)
s = input()
    print(s.count('1'))

### FIXED CODE ###

s = input()
print(s.count('1'))
from collections import deque

N,K=map(int,input().strip().split())
x=list(map(int,input().strip().split()))
inf=10*8

l=inf
dp=x[N-K:N-1]
i=0
while N-K-i>=0:
    if dp[0]>=0:
        tmp=dp[K-1]
    elif dp[K-1]<=0:
        tmp=-dp[0]
    else:
        if dp[K-1]>=dp[0]:
            tmp=dp[0]*2+dp[K-1]
        else:
            tmp=dp[K-1]*2+dp[0]
    l=min(l,tmp)
    i+=1
    if N-K-i<0:
        break
    else:
        dp.appendleft(x[N-K-i])
        dp.pop()
print(l)

### FIXED CODE ###

from collections import deque
    
N,K=map(int,input().strip().split())
x=list(map(int,input().strip().split()))
inf=10**9
    
l=inf
dp=deque(x[N-K:N])
i=0
while True:
    if dp[0]>=0:
        tmp=dp[K-1]
    elif dp[K-1]<=0:
        tmp=-dp[0]
    else:
        if abs(dp[K-1])>=abs(dp[0]):
            tmp=abs(dp[0])*2+abs(dp[K-1])
        else:
            tmp=abs(dp[K-1])*2+abs(dp[0])
    l=min(l,tmp)
    i+=1
    if N-K-i<0:
        break
    else:
        dp.appendleft(x[N-K-i])
        dp.pop()
print(l)
a = list(input())
s = list(input())
if a >= 3200:
   print('{}'format.(s))
else:
  print('red')

### FIXED CODE ###

a = int(input())
s = input()
if a >= 3200:
   print((s))
else:
  print('red')
# coding: utf-8
n = input()
list = n.split(" ")
num = [int(x) for x in list ]

print(num.max - num.min)
    

### FIXED CODE ###

# coding: utf-8
n = input()
list = n.split(" ")
num = [int(x) for x in list ]

print(max(num)-min(num))
read=input
r,d,x=map(int,read()).split(' ')
for i in range(10):
  x=int(r*x-d)
  print(x)

### FIXED CODE ###

read=input
r,d,x=map(int,read().split(' '))
for i in range(10):
  x=int(r*x-d)
  print(x)
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

from functools import lru_cache
dhw = [
    [0,1],
    [1,0],
    [0,-1],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and (nh,nw) not in passed and sss[nh][nw]==0:
            ans = min(ans, calc(nh,nw) + 1)
    return ans

print(H * W - sum(map(sum, sss)) - calc(0,0))

### FIXED CODE ###

from collections import defaultdict, deque
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

dhw = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
]

# h,w,dist
dq = deque([(0, 0, 0)])
# h,w
queued = {(0, 0)}

fdist = -1
while dq:
    h, w, dist = dq.popleft()
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1

        if (nh,nw) in queued:
            continue
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if sss[nh][nw]:
            continue

        dq.append((nh, nw, ndist))
        queued.add((nh, nw))

if fdist == -1:
    print(-1)
else:
    print(H * W - sum(sum(sss,[])) - fdist - 1)
import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
    V = list(map(int,input().split()))
    
    ans = -(10**10)
    for pick in range(K+1):
        throw = min(pick,K-pick)
        for left in range(pick+1):
            right = pick-left
            p = []
            minus = 0
            for i in range(left):
                if V[i] < 0:
                    minus += 1
                p.append(V[i])
            for i in range(right):
                if V[-i-1] < 0:
                    minus += 1
                p.append(V[-i-1])
            p.sort()
            if minus >= throw:
                rest = p[throw:]
            else:
                rest = p[minus:]
            ans = max(ans,sum(rest))
    
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
    V = list(map(int,input().split()))
    
    ans = -(10**10)
    for pick in range(min(N+1,K+1)):
        throw = min(pick,K-pick)
        for left in range(pick+1):
            right = pick-left
            p = []
            minus = 0
            for i in range(left):
                if V[i] < 0:
                    minus += 1
                p.append(V[i])
            for i in range(right):
                if V[-i-1] < 0:
                    minus += 1
                p.append(V[-i-1])
            p.sort()
            if minus >= throw:
                rest = p[throw:]
            else:
                rest = p[minus:]
            ans = max(ans,sum(rest))
    
    print(ans)
    
if __name__ == "__main__":
    main()
a, b = input().split()
a = int(a)
b = int(100 * int(b.split('.')))


def solve(a, b):
    return a * b // 100


print(solve(a, b))


### FIXED CODE ###

a, b = input().split()
a = int(a)
b, c = map(int, b.split('.'))


def solve(a, b):
    return a * (b * 100 + c) // 100


print(solve(a, b))
a,b,c = list(map(int,input().split()))
 
if a < b:
    if b < c:
        print(a < b < c)
    else:
        print("a < c < b")
    else:
        print("c < a < b")
elif a > b:
    if a > c:
        if b < c:
            print("b < c < a")
        else:
            print("c < b < a")
    else:
        print("b < c < a")

### FIXED CODE ###

num = list(map(int, input().split()))

num.sort()

print(num[0], num[1], num[2])
a=int(input())
b=int(input())
print(f"{a*b} {(a+b)*2}")


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,(a+b)*2)
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

L.sort(key=lambda x:x[2])

for x in range(101):
    for y in range(101):
        h = L[-1][2] + abs(x-L[-1][0]) + abs(y-L[-1][1])
        for l in L: 
            if l[2] == 0:
                if h - (abs(x-l[0]) + abs(y-l[1])) > 0:
                    flag = 0
                    break
            else:
                if h == -1:
                    tmp = l[2] + abs(x-l[0]) + abs(y-l[1])
                h = l[2] + abs(x-l[0]) + abs(y-l[1])
                
                if tmp == h:
                    flag = 1
                    tmp = h
                else:
                    flag = 0
                    break
                
                
        if flag == 1:
            gx = x
            gy = y
            gh = h
            break
                
                    
    if flag == 1:
        break
        
print(gx, gy, gh)

### FIXED CODE ###

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

L.sort(key=lambda x:x[2])

for x in range(101):
    for y in range(101):
        h = L[-1][2] + abs(x-L[-1][0]) + abs(y-L[-1][1])
        for l in L: 
            if l[2] == 0:
                if h - (abs(x-l[0]) + abs(y-l[1])) > 0:
                    flag = 0
                    break
            else:

                if h == l[2] + abs(x-l[0]) + abs(y-l[1]):
                    flag = 1
                
                else:
                    flag = 0
                    break
                
                
        if flag == 1:
            gx = x
            gy = y
            gh = h
            break
                
                    
    if flag == 1:
        break
        
print(gx, gy, gh)
if(input()) == 0:
print(0)
else:
print(1)

### FIXED CODE ###

if int(input())==1:
    print(0)
else:
    print(1)
#coding: utf-8
def dot(a, b):
    return (a.real*b.real - a.imag*b.imag)
def cross(a, b):
    return (a.real*b.imag - a.imag*b.real)

EPS = 10**(-7)

def isIntersectedLS(a1, a2, b1, b2):
    return ((cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1)) < EPS and
            (cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1)) < EPS)

while 1:
    try:
        x,y = [[0 for i in xrange(3)] for j in xrange(2)]
        a = []
        z = [0 for i in xrange(2)]
        x[0],y[0],x[1],y[1],x[2],y[2],z[0],z[1] = map(float, raw_input().split())
        for i in xrange(3):
            a.append((x[i]+(y[i])*1j))
        c = (sum(x)/3)+(sum(y)/3)*1j
        p = z[0]+z[1]*1j
            
        for i in xrange(3):
            #print a, c, p
            if isIntersectedLS(a[i-1], a[i], c, p) is True:
                print "NO"
                break
        else:
            print "YES"
            
    except EOFError:
        break

### FIXED CODE ###

def dot(a, b):
    return (a.real*b.real - a.imag*b.imag)
def cross(a, b):
    return (a.real*b.imag - a.imag*b.real)

EPS = 10**(-7)

def isIntersectedLS(a1, a2, b1, b2):
    return ((cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1)) < EPS and
            (cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1)) < EPS)

while 1:
    try:
        x,y = [[0. for i in xrange(3)] for j in xrange(2)]
        a = []
        z = [0. for i in xrange(2)]
        line = raw_input().split()
        if line == []: break
        x[0],y[0],x[1],y[1],x[2],y[2],z[0],z[1] = map(float, line)
        for i in xrange(3):
            a.append((x[i]+(y[i])*1j))
        c = (sum(x)/3)+(sum(y)/3)*1j
        p = z[0]+z[1]*1j
           
        for i in xrange(3):
            #print a, c, p
            if isIntersectedLS(a[i-1], a[i], c, p) is True:
                print "NO"
                break
        else:
            print "YES"
           
    except EOFError:
        break
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import heapq
n,k=IL()
nl=dict()
for i in range(n+1):
    nl[i]=0
l=[]
ans=[]
f=[]
el=[]
heapq.heapify(el)
s=0
for i in range(n):
    t,d=IL()
    l.append([d,t])
l.sort(reverse=True)
for i in range(k):
    t=l.pop(0)
    el.heappush(t)
    nl[t[1]]+=1
    s+=t[0]
    if t[1] not in f:
        f.append(t[1])
u=len(f)
ans.append(s+u*u)
for i in range(u,k+1):
    if len(l)==0:
        break
    while True:
        t=el.heappop(0)
        if nl[t[1]]!=1:
            nl[t[1]]-=1
            s-=nl[t[0]]
            break
    while len(l)>0:
        t=l.pop(0)
        if nl[t[1]]==0:
            nl[t[1]]+=1
            s+=t[0]
            el.heappush(t)
            break
    ans.append(s+(u+i+1)**2)
    if len(l)==0:
        break
print(max(ans))

### FIXED CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n,k=IL()
top=dict()
sub=[]
for i in range(n):
    t,d=IL()
    if t in top:
        sub.append(min(top[t],d))
        top[t]=max(top[t],d)
    else:
        top[t]=d

top=sorted(top.items(),key=lambda x:-x[1])
sub.sort(reverse=True)

rtop=[top[0][1]]
rsub=[0]
for i in range(1,len(top)):
    rtop.append(rtop[-1]+top[i][1])
for i in range(len(sub)):
    rsub.append(rsub[-1]+sub[i])

ans=0
for i in range(k):
    if i<len(rtop) and 0<=k-i-1<len(rsub):
        ans=max(ans,rtop[i]+rsub[k-i-1]+(i+1)**2)
print(ans)
n = map(int,input.split())
l = [int(x) for x in input().split()]

s = sum(l)
res = "Yes"
for x in l:
  if (2*x>=s):
    res = "No"
print(res)
    

### FIXED CODE ###

n = map(int,input().split())
l = [int(x) for x in input().split()]

s = sum(l)
res = "Yes"
for x in l:
  if (2*x>=s):
    res = "No"
print(res)
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
            if a[i][j:j+3] == ["#","#","#"]:
                if a[i+2][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
        for k in range(1,w):
            if a[i][k] == "#":
                if a[i+1][k-2:k] == ["#","#"]:
                    print("Impossible")
                    exit()
    if a[h-2][-1] == "#":
        if a[h-1][-2] == "#":
            print("Impossible")
            exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()
d = [2,5,5,4,5,6,3,7,6]

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = find(N - d[a - 1])
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)
        else:
            continue

        if len(mval) < len(val) or (len(mval) == len(val) and mval < val):
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)


### FIXED CODE ###

import sys
sys.setrecursionlimit(150000)


d = [2,5,5,4,5,6,3,7,6]

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = find(N - d[a - 1])
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)
        else:
            continue

        if len(mval) < len(val) or (len(mval) == len(val) and mval < val):
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)
def main():
    # N, M = list(map(int, input().split()))
    # inputs = [input().split() for i in range(M)]
    with open('./abc151/test.txt', 'r') as f:
        inputs = f.read()
        f.close()
    inputs = inputs.split()
    inputs = [[inputs[i], inputs[i + 1]] for i in range(0, len(inputs), 2)]
    print(inputs)
    has_been_solved = set()

    penalty = 0
    correct = 0
    for i in inputs:
        num = int(i[0])
        if num not in has_been_solved and i[1] == 'AC':
            has_been_solved.add(num)
        elif num not in has_been_solved and i[1] != 'AC':
            penalty += 1
    correct = len(has_been_solved)
    
    print(correct, penalty)            
        

if __name__ == "__main__":
    main()


### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*n
w=[0]*n
ac=0
wc=0
for _ in range(m):
    p,s=input().split()
    p=int(p)-1
    if a[p]==0:
        if s=='AC':
            a[p]=1
            ac+=1
            wc+=w[p]
        else:
            w[p]+=1
print(ac,wc)
S = int(input())
s = s % 60
m = s // 60 % 60
h = s // 60 // 60

print("{0}:(1):(2)",format (h,m,s)

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format (h,m,s))
N = int(input())
W = list(map(int, input().split()))
dif = [sum(W[:T + 1] - W[T + 1:]) for T in range(N)]
print(min(dif))

### FIXED CODE ###

N = int(input())
W = list(map(int, input().split()))
dif = [abs(sum(W[:T + 1]) - sum(W[T + 1:])) for T in range(N - 1)]
print(min(dif))
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N = i()
A = [26**i for i in range(1,100)]
A = [0]+list(itertools.accumulate(A))
cnt = 0
for i in range(N):
    if A[i] >= N:
        p = cnt
        break
    cnt += 1
if p == 1:
    print(chr(N+96))
    exit()
s = []
if N in A:
    print('z'*p)
    exit()
for i in range(p-1):
    m = chr(N%26+96)
    if m == '`':
        m = 'a'
    s.append(m)
    N = N//26
    print(N%26)
s.append(chr(N+96))
s.reverse()
print(''.join(s))

### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
S = []
for i in range(1,100):
    if N < 27:
        break
    N -= 1
    S.append(chr(ord('a')+N%26))
    N = N//26
S.append(chr(ord('a')+N-1))
print(''.join(S[::-1]))
from fraction import gcd
n = int(input())

ans = 1
for i in range(n):
    t = int(input())
    ans = ans * t // gcd(ans, t)

print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())

ans = 1
for i in range(n):
    t = int(input())
    ans = ans * t // gcd(ans, t)

print(ans)
x,n = [int(x) for x in input().split()]
if n == 0:
  print(x)
else:
  p = [int(x) for x in input().split()]
  p.sort()
  ans = []
  for i in range(1,101):
    if i in p:
      continue
    b = abs(x - i)
    ans.append([i,b])
  ans = sorted(ans,key = lambda x: x[1])
  #print(ans)
  print(ans[0][0])

### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))
for d in range(X + 1):
  for s in [-1, +1]:
    a = X + s * d
    if p.count(a) == 0:
      print(a)
      exit(0)
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def lmc(a, b):
    return a * b // gcd(a, b)

n, m = map(int, input().split())
s = str(input())
t = str(input())
l = lmc(n, m)
L = [0] * l
for i in range(n):
    L[i*(l//n)] = s[i]
for j in range(m):
    if L[j*(l//m)] == 0 or L[j*(l//m)] == t[j]:
        L[j*(l//m)] = t[j]
    else:
        print(-1)
        break
else:
    print(l)


### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def lcm(a, b):
    return a * b // gcd(a, b)

n, m = map(int, input().split())
s = str(input())
t = str(input())
g = gcd(n, m)
l = lcm(n, m)
for i in range(g):
    if s[i*n//g] != t[i*m//g]:
        print(-1)
        break
else:
    print(l)
from itertools import accumulate

N = int(input())
A = list([int(x) for x in input().split()])

count = 0
while True:
    # 中心に最も近い点を探す
    ironbar = list(accumulate(A))
    center = sum(A) // 2

    i = 0
    j = len(A) - 1

    while i + 1 < j:
        check = ironbar[(i + j) // 2]
        if check < center:
            i = (i + j) // 2
        elif check > center:
            j = (i + j) // 2
        else:
            print(count)
            exit()

    if check > center:
        A[j] -= 1
    else:
        A[j] += 1

    count += 1


### FIXED CODE ###

from itertools import accumulate

N = int(input())
A = list([int(x) for x in input().split()])

count = 0
ironbar = list(accumulate(A))

min_value = ironbar[-1]
for i in range(N):
    bet = abs(ironbar[i] - (ironbar[-1] - ironbar[i]))

    if min_value > bet:
        min_value = bet
    else:
        print(min_value)
        exit()
import collections

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = collections.deque()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.append(0)
    q.append(0)
    d[0][0] = 0

    while True:
        px = q.popleft()
        py = q.popleft()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.append(nx)
                    q.append(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

### FIXED CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)