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

# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

A.sort(reverse=True)
F.sort()

q = []
ws = []
cnt = 0

for i in range(N):
    heappush(q, (-A[i]*F[i], A[i], F[i]))
    ws.append(A[i]*F[i])

ws.append(0)
ws.sort(reverse=True)

# print(ws)

for w in ws[1:]:
    # print(w)
    while True:
        # print(w, q)
        val, a, f = heappop(q)
        if val == 0:
            print(-val)
            sys.exit()
        if -val <= w:
            heappush(q, (-a*f, a, f))
            break
        else:
            # a * f < wになるまでaを減らす
            a_n = w // f
            if w== 0:
                diff = 1
            else:
                diff = min(K - cnt, a - a_n)
            cnt += diff
            a -= diff
            heappush(q, (-a*f, a, f))
        # print(w, cnt)
        if cnt >= K:
            break

# print(q)
val, a, f = heappop(q)
print(-val)


### FIXED CODE ###

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

A.sort(reverse=True)
F.sort()


def judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = -1

while lb + 1 < ub:
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(ub))
### BUGGY CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
ans = L[0]
while k-1 > 0:
    ans = L[ans-1]
    k -= 1
print(ans)

### FIXED CODE ###

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

already = [False] * N
step = 0
now = 1
count = 0
while(already[now-1] != True):
    already[now - 1] = True
    now = A[now - 1]
    count += 1
    if count == K:
      print(now)
      exit(0)
loop = 0
cycle = 0
if(now == 1):
    step = 0
    cycle = count
    loop = K % cycle
else:
    step = 0
    temp = 1
    while(temp != now):
        temp = A[temp - 1]
        step += 1
    cycle = count - step
    loop= (K - step) % cycle

temp = 1
for i in range(step + loop):
    temp = A[temp - 1]
print(temp)
### BUGGY CODE ###

n=int(input())
x=""
while n!=0:
    x=str(n%2)+x
    s=-(n//2)
print(0 if x=="" else x)

### FIXED CODE ###

n=int(input())
x=""
while n!=0:
    x=str(n%2)+x
    n=-(n//2)
print(0 if x=="" else x)
### BUGGY CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0,2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dx=[0,0,1,-1,0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    
    for i in range(24):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if abs(ny-y)+abs(nx-x)==1:
          if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
            q.append((ny,nx))
            D[ny][nx]=D[y][x]
        else:
          if A[ny][nx]=='.':
            if D[ny][nx]==10**8:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
            elif D[ny][nx]>D[y][x]+1:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

### FIXED CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][mx]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])
### BUGGY CODE ###

from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [[[] for _ in range(2)] for _ in range(N)]
for m in AB:
    F[m[0] - 1][0].append(m[1] - 1)
    F[m[1] - 1][0].append(m[0] - 1)
for k in CD:
    F[k[0] - 1][1].append(k[1] - 1)
    F[k[1] - 1][1].append(k[0] - 1)

L = [0] * N
m = [[] for _ in range(N)]

for i in range(N):
    if L[i] != 0:
        continue
    l = []
    c = 0
    d = [0] * N
    d[i] = 1
    l.append(i)
    Q = deque()
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in range(len(F[q][0])):
            a = F[q][0][j]
            if d[a] == 1:
                continue
            d[a] = 1
            c += 1
            Q.append(a)
            l.append(a)
    m[i] = l
    for j in l:
        L[j] = c
        m[j] = l

for i in range(N):
    print(L[i] - len(F[i][0]) - len(set(F[i][1]) & set(m[i])), end=' ')

print('')

### FIXED CODE ###

import time
from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [set() for _ in range(N)]
B = [set() for _ in range(N)]

for i, j in AB:
    F[i - 1].add(j - 1)
    F[j - 1].add(i - 1)
for i, j in CD:
    B[i - 1].add(j - 1)
    B[j - 1].add(i - 1)

Q = deque()
S = [0] * N
d = [0] * N

for i in range(N):
    if d[i] != 0:
        continue
    L = {i}
    d[i] = 1
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in F[q]:
            if d[j] == 0:
                d[j] = 1
                Q.append(j)
                L.add(j)
    for k in L:
        S[k] = len(L) - len(L & F[k]) - len(L & B[k]) - 1

print(*S)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
xy=np.reshape(np.array(xy),(n,2))
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

## B - Iron Bar Cutting
N = int(input())
A = list(map(int, input().split()))
ans = []
for n in range(1,N):
    ans.append(abs(sum(A[:n]) - sum(A[n:])))
print(min(ans))

### FIXED CODE ###

## B - Iron Bar Cutting
N = int(input())
A = list(map(int, input().split()))
L = 0
R = sum(A)
ans = sum(A)
for n in range(N):
    L += A[n]
    R -= A[n]
    if ans > abs(L-R):
        ans = abs(L-R)
print(ans)
### BUGGY CODE ###

def kitaichi(a):
    sum = 0
    for i in range(a):
        sum += i+1
    return sum / a

n, k = map(int, input().split())
p = [int(_) for _ in input().split()]
lis = [0] * n

for i in range(n):
    lis[i] = kitaichi(p[i])

val = 0
ans = 0

for i in range(0, n-k+1):
    val = 0
    for j in range(k):
        val += lis[i+j]
    ans = max(ans, val)

print(ans)

### FIXED CODE ###

def kitaichi(a):
    return ((1+a)*a/2)/a

n, k = map(int, input().split())
p = [int(_) for _ in input().split()]
dp = [0] * n
dp[0] = p[0]
cnt = 1

maxi = 0
idx = 0

for i in range(1, n):
    if cnt < k:
        dp[i] = p[i] + dp[i-1]
        cnt += 1
    else:
        dp[i] = p[i] + dp[i-1] - p[i-k]
    if maxi < dp[i]:
        maxi = dp[i]
        idx = i

ans = 0
for i in range(idx-k+1, idx+1):
    ans += kitaichi(p[i])

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

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

duplicate_list = [x for x in set(An) if An.count(x) > 1]

if duplicate_list:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

N = int(input())
An = list(map(int, input().split()))
Bn = sorted(An)

y = -1
count = 0
for x in Bn:
    if x == y:
        count += 1
    y = x

if count == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N = int(input())
n_list = list(map(int, input().split()))
n_sum = 0
for i in range(N):
    for j in range(0, i):
        n_sum += n_list[i] ^ n_list[j]
print(n_sum % (10**9 + 7))

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()] , dtype=np.int64)
m = 10**9+7
ans = 0
for k in range(60):
    b = (a>>k) & 1
    res = np.count_nonzero(b)
    ans += res*(n-res)*2**k
print(ans%m)
### BUGGY CODE ###

a, b, k = map(int, input().split())
l = [i for i in range(a, b+1)]

ans = []
for i in l[:k]:
    ans.append(i)

for i in l[len(l)-k:]:
    if not(i in ans):
        ans.append(i)

for i in ans:
    print(i)


### FIXED CODE ###

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

ans = []
for i in range(a, a+k):
    if i > b:
        break
    ans.append(i)

for i in range(b-k+1, b+1):
    if i < a:
        break
    if not(i in ans):
        ans.append(i)

for i in ans:
    print(i)
### BUGGY CODE ###

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

memo = dict()
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    if memo.get((l, r, wl, wr)):
        return memo[(l, r, wl, wr)]
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    memo[(l, r, wl, wr)] = v
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=None)
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])
### BUGGY CODE ###

def main():
    n=int(input())
    s=input()
    dp=[(n+1)*[0]for _ in range(n+1)]
    ans=0
    for i in range(1,n):
        for j in range(i+1,n+1):
            if s[i-1]==s[j-1]:
                dp[i][j]=min(dp[i-1][j-1]+1,j-i)
                ans=max(ans,dp[i][j])
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append([s-x-0.5,1,x])
    TT.append([t-x-0.5,-1,x])
for i in range(Q):
    d = ri()
    TT.append([d,0,i])


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

### FIXED CODE ###

import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
C1 = C_T[0]
for C2 in C_T[1:]:
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        cost = dp[j][0]
        for k in range(H+1):
            cost += (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            cost = min(dp[j][k+1], cost)
            dp[j][k+1] = cost
    ans += dp[H][H]
    C1 = C2
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

import math
k = int(input())
ans = 0

for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans = ans + math.gcd(math.gcd(i,j),l)

print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0

for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans = ans + math.gcd(math.gcd(i,j),l)

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

import math

S = int(input())

ans = [0, 0]
seki = S + 10 ** 9
for i in range(10 ** 4, 10**9):
    div = seki % i
    if div == 0:
        if seki // i > 10 ** 9:
            continue
        ans += [i, 1, 10 ** 9, seki // i]
        print(*ans)
        exit()


### FIXED CODE ###

import math

S = int(input())

ans = [0, 0]
if S <= 10 ** 9:
    ans += [S, 0, 0, 1]
else:
    root = math.ceil(math.sqrt(S))
    ans += [root ** 2 - S, root, root, 1]

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

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

Hx=[] #爆破対象の座標を記録
Hy=[]
X=[]
for i in range(M):
    h,w=map(lambda x:int(x)-1,input().split())
    Hx.append(h)
    Hy.append(w)
    X.append([h,w])

sum_c=[0]*W #縦の合計
sum_r=[0]*H #横の合計
for i in Hy:
    sum_c[i] += 1
for j in Hx:
    sum_r[j] += 1

max_c=max(sum_c)
max_r=max(sum_r)

flag=0 #max_cの列とmax_rの行で交差点に爆弾がないところがあればflag=1
for i in range(H):
    for j in range(W):
        if sum_r[i]==max_r and sum_c[j]==max_c:
            if [i,j] not in X:
                flag=1
                break
    if flag==1:
        break

if flag==0:
    print(max_c+max_r-1)
else:
    print(max_c+max_r)

### FIXED CODE ###

H, W, M = map(int, input().split())
row=[0]*H #x座標を入れるっちゅうかカウント
col=[0]*W #y座標を入れる
 
mat=[] #座標を入れる
 
for i in range(M):
    h, w = map(int, input().split())
    row[h-1]+=1
    col[w-1]+=1
    mat.append((h-1,w-1))
r=max(row)
c=max(col)
 
rr=[1 if row[i]==r else 0 for i in range(H)] #maxな列のインデックス
cc=[1 if col[i]==c else 0 for i in range(W)] #maxな行のインデックス
 
x=0 #maxな列と行の交差点にある爆弾の個数をカウント
for k in mat:
    if rr[k[0]]==1 and cc[k[1]]==1:
        x+=1
        
if sum(rr)*sum(cc)==x: #行と列の全ての交差点に爆弾があれば-1する
    print(r+c-1)
else:
    print(r+c)
### BUGGY CODE ###

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

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])

while (length > 0):
    gray = []
       
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
    
    gray2 = list(map(list, set(map(tuple, gray))))
    
    for l in gray2:
        black.append(l)
        white.remove(l)
        A[l[0]][l[1]] = "#"
        
    cnt += 1
    length = len(white)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

from collections import deque
n = int(input())
P = list(map(int, input().split()))
INF = 10**18
MAP = ['#']*(n**2)
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*(n**2)
    dist[to_v(*init_v)] = 0
    MAP[to_v(*init_v)] = '.'
    mincost = INF
    while next_v:
        i, j = next_v.popleft()
        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                if dist[to_v(i, j)] < mincost:
                    mincost = dist[to_v(i, j)]
                continue
            cost = 0 if MAP[to_v(x, y)] == '.'else 1
            if dist[to_v(x, y)] <= dist[to_v(i, j)]+cost:
                continue
            dist[to_v(x, y)] = dist[to_v(i, j)]+cost
            next_v.append((x, y))
    return dist, mincost


def to_idx(p):
    i, j = divmod(p-1, n)
    return i, j


def to_v(i, j):
    return i*n+j


ans = 0
for p in P:
    dist, mincost = bfs(to_idx(p))
    ans += mincost
print(ans)


### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a + b)

AB.sort(reverse=True)
AB = AB[:min(3001, X * Y * Z + 1)]
ABC = []
for ab in AB:
  for c in C:
    ABC.append(ab + c)
ABC.sort(reverse=True)
print(*ABC[:K], sep='\n')


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a + b)

AB.sort(reverse=True)
AB = AB[:min(3001, X * Y * Z + 1)]
ABC = []
for c in C:
  for ab in AB:
    ABC.append(ab + c)
ABC.sort(reverse=True)
for i in range(K):
  print(ABC[i])