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

from bisect import bisect_left, insort_left
from collections import deque
import sys
readlines = sys.stdin.readline
def main():
	x,y,a,b,c = map(int,input().split())

	p = list(map(int,input().split()))
	q = list(map(int,input().split()))
	r = list(map(int,input().split()))

	p.sort()
	q.sort()
	r.sort(reverse=True)

	p = p[a-x:]
	q = q[b-y:]
	ans = sum(p) + sum(q)
	p_count = 0
	q_count = 0

	for i in range(c):
		if p[p_count] < r[i] and q[q_count] < r[i]:
			if p[p_count] < q[q_count]:
				ans -= p[p_count]
				ans += r[i]
				insort_left(p,r[i])
				p_count += 1
			else:
				ans -= q[q_count]
				ans += r[i]
				insort_left(q,r[i])
				q_count += 1
		elif p[p_count] < r[i] and q[q_count] >= r[i]:
			ans -= p[p_count]
			ans += r[i]
			insort_left(p,r[i])
			p_count += 1
		elif p[p_count] >= r[i] and q[q_count] < r[i]:
			ans -= q[q_count]
			ans += r[i]
			insort_left(q,r[i])
			q_count += 1
		else:
			break

	print(ans)
if __name__ == '__main__':
	main()

### FIXED CODE ###

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

p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
q.sort()
r.sort(reverse=True)

p = p[a-x:]
q = q[b-y:]

p.extend(q)
p.sort()

ans = sum(p)
count = 0
for i in range(c):
	if p[i] < r[i]:
		ans += r[i] - p[i]
	else:
		break
print(ans)
### BUGGY CODE ###

n, a, b, k = map(int, input().split())

M = 998244353
fact_n = [None for m in range(n+1)]
fact_inv = [None for m in range(n+1)]


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    c = fact_inv[r] * fact_inv[n-r] % M
    return fact_n[n] * c % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, n+1):
        fact_n[i] = fact_n[i-1] * i % M
        fact_inv[i] = fact_inv[i-1] * pow(i, M-2, M) % M

    com = 0
    for i in range(n+1):
        if (k-a*i) % b == 0 and k - a * i >= 0:
            j = (k-a*i) // b
            com += combination(n, i) * combination(n, j) % M

    print(com % M)

    
if __name__ == '__main__':
    main()


### FIXED CODE ###

n, a, b, k = map(int, input().split())

M = 998244353
fact_n = [0 for m in range(n+1)]
fact_inv = [0 for m in range(n+1)]


def mod_pow(a, n):
    x = 1
    while n > 0:
        if n & 1:
            x = x * a % M

        a = a * a % M
        n >>= 1

    return x


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    return fact_n[n] * fact_inv[r] * fact_inv[n-r] % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, n+1):
        fact_n[i] = fact_n[i-1] * i % M

    fact_inv[n] = pow(fact_n[n], M-2, M)
    for i in range(n-1, 0, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % M

    com = 0
    for i in range(n+1):
        if (k-a*i) % b == 0 and k - a * i >= 0:
            j = (k-a*i) // b
            com += combination(n, i) * combination(n, j) % M

    print(com % M)


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

N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)
      
#print(graph)
max_set=-1
for i in range(N):
  node_list=[-1]*N
  #bfs
  d=1
  queue=[i]
  illegal=False
  while(True):
    new_queue=[]
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.append(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      #print(node_list,new_queue)
      queue=new_queue
      d+=1
      
print(max_set)

### FIXED CODE ###

N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)
      
#print(graph)
max_set=-1
for i in range(N):
  node_list=[-1]*N
  #bfs
  d=1
  queue={i}
  illegal=False
  while(True):
    new_queue=set()
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.add(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      #print(node_list,new_queue)
      queue=new_queue
      d+=1
      
print(max_set)
### BUGGY CODE ###

def gcd(a,b):    #求最大公约数
    if b==0:
        return a
    else:
        return gcd(b,a%b)
a=[]
n=int(input())
mod=1000000007
ans=0
sum=0
s = [int(n) for n in input().split()]
#s=input().split(" ")
for i in range(0, n):
    k=s[i]
    if i==0:
        ans=k
    else:
        u=ans
        ans = ((u * k) // gcd(u, k))
for i in range(0, n):
    sum=(sum+ans//(int(s[i])))%mod
print(sum)


### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
from fractions import*
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)
### BUGGY CODE ###

R, G, B ,N = map(int, input().split())

cnt = 0
for r in range(N//R + 1):
  for g in range((N-r*R)//G + 1):
    if (N - (r*R + g*G)) % B == 0 and  (N - (r*R + g*G)) >= 0:
      cnt += 1
print(cnt)


### FIXED CODE ###

R, G, B ,N = map(int, input().split())

if R==1 and G==1 and B==1:
  print(int((N+2)*(N+1)*(1/2)))
else:
  RGB = [R, G, B]
  RGB.sort(reverse=True)

  R = RGB[0]
  G = RGB[1]
  B = RGB[2]

  cnt = 0
  NR = N//R
  NG = N//G
  for r in range(NR + 1):
    for g in range(NG + 1):
      NrRgG = N - (r*R + g*G)
      if NrRgG < 0:
        break
      elif NrRgG >= 0:
        if NrRgG % B == 0:
          cnt += 1
  print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(2*2**(n-1).bit_length())
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(ans)  
      


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 1000000000000000000: print(-1)
else: print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a = sorted(a)
for i in range(n):
    ans *= a[i]
    if ans > 1000000000000000000:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            u = max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(0,4):
                dp[s][i+1][j+1] =  u
            u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = u
            u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = u
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])
 
if __name__ == "__main__":
    run()

### FIXED CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            u = max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(0,4):
                dp[s][i+1][j+1] =  u
            u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = u
            u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = u
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

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

n = int(input())
x = list(map(int, input().split()))
l = sorted(x)
X = {}

for i in range(len(x)):
  y = l[:]
  t = y.pop(i)
  X[t] = y[n//2-1]
  
for i in x:
  print(X[i])


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
l = sorted(x)

for i in x:
  if i <= l[n//2-1]:
    print(l[n//2])
  else:
    print(l[n//2-1])
### BUGGY CODE ###

mod = 998244353
n, s = map(int, input().split())
dp = [0] * (s + 1)
dp[0] = 1
for a in map(int, input().split()):
  pre_dp = dp[:]
  for j in range(s + 1):
    dp[j] = (pre_dp[j] * 2) % mod
    if j >= a:
      dp[j] = (dp[j] + pre_dp[j-a]) % mod
print(dp[-1])

### FIXED CODE ###

import numpy as np

mod = 998244353
n, s = map(int, input().split())
dp = np.zeros((n+1, s+1), dtype=int)
dp[0, 0] = 1
for i, a in enumerate(map(int, input().split())):
  dp[i+1] = dp[i] * 2 % mod
  dp[i+1][a:] = (dp[i+1][a:] + dp[i][:-a]) % mod
print(dp[-1, -1])
### BUGGY CODE ###

def plus_and_check(list):
    sum_up = 0
    for i in range(len(list)-1):
        sum_up += list[i]
    i = 0
    while i < 8:
        number_1 = 10 * i
        number_2 = 10 * (i+1)
        if number_2  > sum_up and number_1 < sum_up:
            break
        else:
            continue
        i = i + 1
    return i

l = map(int, raw_input().split())
print "%d" % plus_and_check(l)

### FIXED CODE ###

import sys

a = []
answer_array = []
for line in sys.stdin:
    a.append(map(int, line.strip().split()))
    #except StopIteration:
        #break

for i in range(len(a)):
    sum_up = a[i][0] + a[i][1]

    answer = len(str(sum_up))

    answer_array.append(answer)

for j in range(len(answer_array)):
    print answer_array[j]
### BUGGY CODE ###

class SegTree():
    def segfunc(self, x, y):
        return x | y
        
    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n = int(input())
    s = input().rstrip()
    q = int(input())
    ans = []
    init = [set() for _ in range(n)]
    for i in range(n):
        c = s[i]
        init[i].add(c)
    seg = SegTree(set(), n, init)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y)
            y -= 1
            buf = set()
            buf.add(z)
            seg.update(y, buf)
        else:
            y = int(y)
            y -= 1
            z = int(z)
            ans.append(len(seg.query(y, z)))
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left, insort
def main():
    n = int(input())
    s = list(input().rstrip())
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i, c in enumerate(s):
        al[ord(c) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = bisect_left(al[ord(s[y])-ord("a")],y)
            al[ord(s[y])-ord("a")].pop(p)
            insort(al[ord(z)-ord("a")],y)
            s[y] = z
        else:
            y = int(y) - 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

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

def f(t):
    return t

s=input()
q=int(input())
queri=[]
rv=0

for i in range(q):
    tmp=list(map(f,input().split()))
    queri.append(tmp)
    if tmp[0]=="1": rv+=1
rv=rv%2

if rv==1: s=s[::-1]
ans=[s]

for i in range(q):
    if queri[i][0]=="2":
        rvt=(rv+int(queri[i][1]))%2
        if rvt==1: ans=[queri[i][2]]+ans
        else: s=ans.append(queri[i][2])

    else: rv=(rv+1)%2

for i in range(len(ans)):
    print(ans[i],end="")

### FIXED CODE ###

s=input()
q=int(input())
queri=[]
rv=0
forward=[]
back=[]
for i in range(q):
    queri=list(map(lambda x:x,input().split()))
    if queri[0]=="2":
        rvt=(rv+int(queri[1]))%2
        if rvt==1: forward.append(queri[2])
        else: back.append(queri[2])

    else: rv=(rv+1)%2

if rv==0:
    for i in range(len(forward)-1,-1,-1):
        print(forward[i],end="")
    print(s,end="")
    for i in range(len(back)):
        print(back[i],end="")
        
if rv==1:
    for i in range(len(back)-1,-1,-1):
        print(back[i],end="")
    print(s[::-1],end="")
    for i in range(len(forward)):
        print(forward[i],end="")
### BUGGY CODE ###

moji=input()
moji_rev=moji[::-1]
cycle=int(input())
flont_or_back=0
for i in range(cycle):
    line=input()
    if line[0]=="1":
        flont_or_back+=1
    elif line[0]=="2":
        fi,ci=line[2],line[4]
        if flont_or_back%2==0:
            if fi=="1":
                moji=ci+moji
                moji_rev+=ci
            elif fi=="2":
                moji=moji+ci
                moji_rev=ci+moji_rev
        else:
            if fi=="1":
                moji+=ci
                moji_rev=ci+moji_rev
            elif fi=="2":
                moji=ci+moji
                moji_rev+=ci
if flont_or_back%2==0:
  print(moji)
else:
  print(moji_rev)

### FIXED CODE ###

def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

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

# 愚直に全探索する場合（計算量はn^3）
n = int(input())
A = list(int(i) for i in input().split())  
B = list(int(i) for i in input().split())  
C = list(int(i) for i in input().split())

count = 0
for a in A:
    for b in B:
        for c in C:
            if (a < b and b < c): 
                count += 1

print(count)

### FIXED CODE ###

# 二分探索法を利用する場合
from bisect import bisect_left, bisect_right

N = int(input())
A = list(int(i) for i in input().split())  
B = list(int(i) for i in input().split())  
C = list(int(i) for i in input().split())

# sortの計算量はO(nlogn)
A.sort()
B.sort()
C.sort()

ans = 0
for i in range(N):
    x = bisect_left(A,B[i])
    y = bisect_right(C,B[i])
    ans += x*(N-y)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
DI={}
for i in A:
  if i not in DI:
    DI[i]=1
  else:
    DI[i]+=1  
d=0
B=sorted(list(set(A)))
n=len(B)
for i in range(n):
  if DI[B[i]]!=1:
    continue
  d+=1
  for j in range(0,i):
    if B[i]<B[j]*2:
      break
    if B[i]%B[j]==0:
      d-=1
      break
print(d)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
D=[1]*(A[-1]+1)
for i in A:
  if D[i]==1:
    for j in range(A[-1]//i):
      D[i*(j+1)]=0
    D[i]=1
dic={}
for i in A:
  if i not in dic:
    dic[i]=1
  else:
    dic[i]+=1

for i in dic:
  if dic[i]>1:
    D[i]=0
    
ans=0
for i in A:
  if D[i]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

def f_d():
    n, q = map(int, input().split())

    t = [[] for _ in range(n+1)]
    o = [0 for _ in range(n)]

    for _ in range(1, n):
        a, b = map(int, input().split())
        t[a].append(b)

    for _ in range(q):
        p, x = map(int, input().split())
        o[p-1] += x
        s = list(t[p])
        while True:
            if len(s) == 0:
                break
            m = s.pop()
            o[m-1] += x
            if len(t[m]) != 0:
                s = s + t[m]

    print(" ".join(map(str, o)))

if __name__ == "__main__":
    f_d()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)
### BUGGY CODE ###

from collections import deque

H, W = list(map(int, input().split()))


masu = [input() for _ in range(H)]

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break

    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        # visited[tmpy][tmpx] = True

        # if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
        if not(tmpx in range(W)) or not(tmpy in range(H)):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
else:
    print(-1)
    exit()
# print(sum(visited[4]))
print(H * W - kuro - cost - 1)


### FIXED CODE ###

from collections import deque

H, W = list(map(int, input().split()))


masu = [input() for _ in range(H)]

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    # print(i, j)

    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break
    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        # visited[tmpy][tmpx] = True

        # if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
        if not(tmpx in range(W)) or not(tmpy in range(H)):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
            visited[tmpy][tmpx] = True
else:
    print(-1)
    exit()
# print(sum(visited[4]))
print(H * W - kuro - cost - 1)