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

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s)

    # %%
    if answer == INF:
        print(-1)
    else:
        print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))
### BUGGY CODE ###

import copy
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    c = [[None]*w for _ in range(h)]
    for i in reversed(range(h)):
        for j in reversed(range(w)):
            c[i][j] = abs(a[i][j] - b[i][j])
            if i < h-1:
                c[i][j] += c[i+1][j]
            if j < w-1:
                c[i][j] += c[i][j+1]
    dp = [set() for i in range(w)]
    dp[0].add(abs(a[0][0] - b[0][0]))
    for j in range(1, w):
        x = abs(a[0][j] - b[0][j])
        for v in dp[j-1]:
            dp[j].add(v + x)
            dp[j].add(abs(v - x))
    for i in range(1, h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if j == 0:
                buf = copy.deepcopy(dp[j])
                dp[j].clear()
                for v in buf:
                    dp[j].add(v + x)
                    dp[j].add(abs(v - x))
            else:
                buf = dp[j-1] | dp[j]
                dp[j].clear()
                for v in buf:
                    dp[j].add(v + x)
                    dp[j].add(abs(v - x))
    ans = float("inf")
    for v in dp[w-1]:
        ans = min(ans, abs(v))
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
inf=float("inf")
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sx in range(H):
    for sy in range(W):
        for gx in range(H):
            for gy in range(W):
                if S[sx][sy]==S[gx][gy]==".":
                    data=[[inf]*W for i in range(H)]
                    que=[[sx,sy]]
                    data[sx][sy]=0
                    count=1
                    while que:
                        h=[]
                        for x,y in que:
                            for dx,dy in d:
                                nx,ny=x+dx,y+dy
                                if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                                    h.append([nx,ny])
                                    data[nx][ny]=count
                        que=h
                        count+=1
                    ans=max(ans,data[gx][gy])
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
inf=float("inf")
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy]==".":
            data=[[inf]*W for i in range(H)]
            que=[[sx,sy]]
            data[sx][sy]=0
            count=1
            while que:
                h=[]
                for x,y in que:
                    for dx,dy in d:
                        nx,ny=x+dx,y+dy
                        if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                            h.append([nx,ny])
                            data[nx][ny]=count
                que=h
                count+=1
            for i in range(H):
                for j in range(W):
                    if data[i][j]!=inf:
                        ans=max(ans,data[i][j])
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
import collections

sys.setrecursionlimit(1000000)

class UnionFind2:
    def __init__(self, size):
        # 負の値はルート (集合の代表)
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1
            return True
        return False


N, M = map(int, input().split())
uf = UnionFind2(N)

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

hoge = [uf.find(i) for i in range(N)]

# print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])


### FIXED CODE ###

import sys
from collections import defaultdict
import collections

sys.setrecursionlimit(1000000)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        self.parents[y] = x


N, M = map(int, input().split())
uf = UnionFindPathCompression(N)

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A - 1, B - 1)

hoge = [uf.find(i) for i in range(N)]

#print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def recur(li,i,n,w,dp):
    if i==(n-1):
        if w<=li[i][0]:
            return li[i][1],li[i][1]
        else:
            return 0,0
    if w==0:
        return li[i][1],li[i][1]
    mx=li[i][1]
    for j in range(i+1,n):
        if (w-li[i][0])>=li[j][0]:
            if dp[j][w-li[i][0]]==[-1,-1]:
                val=recur(li,j,n,w-li[i][0],dp)
                dp[j][w-li[i][0]]=val
            else:
                val=dp[j][w-li[i][0]]
            mx=max(mx,val[0]+li[i][1])
    if dp[i+1][w]==[-1,-1]:
        val=recur(li,i+1,n,w,dp)
        dp[i+1][w]=val
    else:
        val=dp[i+1][w]
    overall=max(mx,val[1])
    #print(mx,overall)
    return mx,overall

n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
print(recur(li,0,n,w,dp)[1])

### FIXED CODE ###

from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

def main():
    n,w=[int(x) for x in input().split()]
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    print(recursion(li,0,n,w,dp))
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def gcd(p,q):
    while(q!=0):
        r=p%q
        p=q
        q=r
    return p
    
n=int(input())
sum=0
for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            sum+=gcd(a,gcd(b,c))
print(sum)

### FIXED CODE ###

def gcd(p,q):
    while(q!=0):
        r=p%q
        p=q
        q=r
    return p
    
n=int(input())
sum=0
for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            sum+=gcd(a,gcd(b,c))
print(sum)
### BUGGY CODE ###

n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
if m[0][1] < m[-1][1]:
    for i in range(n):
        m[i][0] = m[i][0] * (-1)
    m.reverse()
bomb = [0 for _ in range(n)]
r = 1
d *= 2
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    bomb[i] = r - 1
res = 0
for i in range(n):
    if m[i][1] > 0:
        tres = (m[i][1] + a - 1) // a
        res += tres
        dh = tres * a
        for j in range(i, bomb[i] + 1):
            m[j][1] -= dh
print(res)


### FIXED CODE ###

from collections import deque
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
q=deque([])
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
tdamage = 0
for i in range(n):
    while q and q[0][0] <= i:
        minus = q.popleft()
        tdamage -= minus[1]
    m[i][1] -= tdamage
    if m[i][1] > 0:
        res += m[i][1]
        tdamage += m[i][1]
        q.append([m[i][2],m[i][1]])
print(res)
### BUGGY CODE ###

from heapq import *
def main():
    N=int(input())
    line = list(input())
    ans=[]

    for i in range(N+1):
        a=line[:i].count("#")
        b=line[i:].count(".")
        heappush(ans,a+b)

    return heappop(ans)

print(main())

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('.')
num = ans
for c in s:
  if c == '.':
    num -= 1
  else:
    num += 1
  
  ans = min(ans,num)

print(ans)
### BUGGY CODE ###

import time
import sys

n = int(input())
s = [input() for _ in range(n)]
t = []
for i in range(n):
    t.append(s[i] + s[i])
t = t + t

start = time.time()

ans = 0
for i in range(n):
    for j in range(n):
        ok = True
        for k in range(n):
            for l in range(k, n):
                if t[i+k][j+l] != t[i+l][j+k]: 
                    ok = False
                    break
            if not ok: break
        if ok: ans += 1
        if time.time() - start > 1600:
            print(n * n)
            sys.exit()
print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
t = []
for i in range(n):
    t.append(s[i] + s[i])
t = t + t
ans = 0
for i in range(n):
    ok = True
    for j in range(n):
        for k in range(n):
            if t[i+j][k] != t[i+k][j]: 
                ok = False
                break
        if not ok: break
    if ok: ans += 1
print(ans * n)
### BUGGY CODE ###

x,y = map(int,input().split())
li = list(map(int,input().split()))
score = 0
for i in range(y):
  li[li.index(max(li))] //= 2
print(sum(li))

### FIXED CODE ###

import heapq

n, m = map(int,input().split())
li = list(map(lambda x: int(x)*(-1),input().split()))

heapq.heapify(li)

for i in range(m):
    a = heapq.heappop(li)
    a = (-a) // 2
    heapq.heappush(li,-a)

print(-sum(li))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
N, K = map(int, input().split())
H = sorted(list(map(int, input().split())), reverse=True)
l = len(H)
if K != 0:
    for i in range(K):
        if len(H)==0:
            print(0)
            sys.exit()
        else:
            H.pop(0)
    if len(H)==0:
        print(0)
    else:
        print(sum(H))
else:
    print(sum(H))

### FIXED CODE ###

#!/usr/bin/env python3
import sys
N, K = map(int, input().split())
H = sorted(list(map(int, input().split())), reverse=True)
l = len(H)
if K != 0:
    if len(H) <= K:
        print(0)
    else:
        print(sum(H[K:]))
else:
    print(sum(H))
### BUGGY CODE ###

s = input()
List = list(s)
n = len(List)
base = [1]*n
for _ in range(10**5):
  temp = [0]*n
  for i in range(n):
    if List[i] == 'R':
      temp[i+1] += base[i]
    else:
      temp[i-1] += base[i]
  base = temp
print(*base)

### FIXED CODE ###

s = input()
List = list(s)+['R']
n=len(List)
R = 0
L = 0
ans = [0]*n
for i in range(n):
  if List[i]=='R':
    R += 1
    if L > 0:
      ans[i-L] += (L+1)//2
      ans[i-L-1] += L//2
      L = 0
  else:
    L += 1
    if R > 0:
      ans[i] +=R//2
      ans[i-1] += (R+1) //2
      R = 0
print(*ans[:-1])
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[set() for i in range(W+1)] for j in range(H+1)]
d[1][1].add(A[0][0]-B[0][0])
d[1][1].add(B[0][0]-A[0][0])
for h in range(H):
    for w in range(W):
        x=A[h][w]-B[h][w]
        for y in d[h][w+1].union(d[h+1][w]):
            d[h+1][w+1].add(y+x)
            d[h+1][w+1].add(y-x)
for i in range(99):
    if i in d[H][W] or -i in d[H][W]:
        print(i)
        exit()

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[0]*W for j in range(H)]
m=80*(H+W)
d[0][0]=1<<m
for h in range(H):
    for w in range(W):
        x=abs(A[h][w]-B[h][w])
        if h>0:
            d[h][w]|=d[h-1][w]
        if w>0:
            d[h][w]|=d[h][w-1]
        d[h][w]=d[h][w]<<x|d[h][w]>>x
x,y=1<<m,1<<m
for i in range(99):
    if d[H-1][W-1]&x or d[H-1][W-1]&y:
        print(i)
        exit()
    x<<=1
    y>>=1
### BUGGY CODE ###

#逆順にしてはやめにbreakできるように
N=int(input())
A=sorted(map(int,input().split()),reverse=True)
c=0
for n in range(N-1):
  if sum(A[n+1:])*2 >= A[n]:
    c+=1
  else:
    break
print(c+1)

### FIXED CODE ###

#累積和で毎回sumしない
N=int(input())
A=sorted(map(int,input().split()))
b=0
c=0
for n in range(N-1):
  b += A[n]
  if b*2 >= A[n+1]:
    c+=1
  else:
    c=0
print(c+1)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
result = 0

# for i, p in enumerate(P):
#     subary = P[:i+1]
#     if (min(subary) >= p):
#         result += 1

for i in range(len(P)):
    subary = P[:i+1]
    if (min(subary) >= P[i]):
        result += 1

print(result)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
result = 0

minValue = P[0]

for i, p in enumerate(P):
  if (minValue >= p):
    result += 1
    minValue = p

print(result)
### BUGGY CODE ###

def main():
    n = int(input())

    s_list = []
    for i in range(n):
        s = sorted(input())
        s_list.append("".join(s))

    count = 0
    for i in range(n-1):
        for j in range(i+1, n):
            if s_list[i] == s_list[j]:
                count += 1

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())

    s_dict = {}
    count = 0
    
    for i in range(n):
        s = sorted(input())
        _s = "".join(s)
        
        if not _s in s_dict:
            s_dict[_s] = 1
        else:
            count += s_dict[_s]
            s_dict[_s] += 1
    print(count)


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

from collections import Counter
S=input()
lenS=len(S)
ans = 0
l = []
for i in range(lenS):
    l.append(int(S[i:])%673)
for k,v in Counter(l).items():
    if k==0:
        ans += v
    else:
        ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

S=list(map(int,input()[::-1]))
lenS=len(S)
cnt = [0]*2019
tmp = 0
for n,i in enumerate(S):
    tmp += i*pow(10,n,2019)
    cnt[tmp%2019]+=1
ans = cnt[0]*(cnt[0]+1)//2
for i in cnt[1:]:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

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

P = []

for i in range(N):
    temp = A.index(i+1) + 1
    temp = str(temp)
    P.append(temp)

print(' '.join(P))


### FIXED CODE ###

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

P = ['']*N

for i in range(N):
    P[A[i]-1] = str(i + 1)


print(' '.join(P))
### BUGGY CODE ###

H,W=map(int,input().split())
INF=10**4
nums=[[INF for i in range(W)] for j in range(H)]
starts=[]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      starts.append([i,j,0])

while starts:
  node=starts.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  if nums[y][x]<=p:
    continue
  for i in range(x,W):
    if nums[y][i]>i-x+p:
      nums[y][i]=i-x+p
    else:
      break
  for i in range(x-1,-1,-1):
    if nums[y][i]>x-i+p:
      nums[y][i]=x-i+p
    else:
      break
  for j in range(y+1,H):
    if nums[j][x]>j-y+p:
      nums[j][x]=j-y+p
    else:
      break
  for j in range(y-1,-1,-1):
    if nums[j][x]>y-j+p:
      nums[j][x]=y-j+p
    else:
      break
  if y-1>=0 and x-1>=0:
    starts.append([y-1,x-1,p+2])
  if y+1<H and x+1<W:
    starts.append([y+1,x+1,p+2])
  if y-1>=0 and x+1<W:
    starts.append([y-1,x+1,p+2])
  if y+1<H and x-1>=0:
    starts.append([y+1,x-1,p+2])

ans=0
for i in range(H):
  ans=max(max(nums[i]),ans)
  
print(ans)
  
  

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

#標準入力受け取り
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(r)

#解法
rewards = 0
li = []
for i in range(M):
    #候補をリストに追加(給料が間に合うもの仕事が一日ごとに増える)
    li.extend(jobs[i])
    if len(li) >0:
        #最大値を求める(給料が高いバイトをしたい)
        reward = max(li)
        rewards += reward
        #使った値は取り除く(同じバイトはNGのため)
        li.remove(reward)

print(rewards)

### FIXED CODE ###

import heapq
#標準入力受け取り
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r)

#解法
rewards = 0
heap = []
for i in range(M):
	for reward in jobs[i]:
		heapq.heappush(heap,reward)

	if len(heap)>0:
		reward = heapq.heappop(heap)
		rewards += -reward

print(rewards)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H and s[ny][nx]=='.':
            q_append((nx,ny,l+1))
else:
    print(-1)
    


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)