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

N,W = map(int,input().split())
array = []
for i in range(N):
    wv = list(map(int,input().split()))
    array.append(wv)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-array[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])

### FIXED CODE ###

N,W = map(int,input().split())
array = []
for i in range(N):
    wv = list(map(int,input().split()))
    array.append(wv)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-array[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
### BUGGY CODE ###

import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n,q = m()

data = [l() for i in range(q)]

edges = [[] for i in range(n)]

for a,b,c in data:
    edges[a-1].append([b-1,c])
    edges[b-1].append([a-1,-c])

num = [0 for _ in range(n)]

Ma,mi = 0,0

vi = [False for i in range(n)]
ans = 0

for i in range(n):
    if vi[i]:
        continue
    stack = [i]
    vi[i] = True
    while stack:
        v = stack.pop()
        for e,r in edges[v]:
            if not vi[e]:
                num[e] = num[v] + r
                stack.append(e)
                vi[e] = True

for i in range(n):
    if num[i] < mi:
        mi = num[i]
    elif num[i] > Ma:
        Ma = num[i]
    for e,r in edges[i]:
        if num[i] + r != num[e]:
            ans = -1
            break
    else:
        continue
    break
else:
    print("Yes")
    exit()
print("No")







### FIXED CODE ###

import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n,q = m()

data = [l() for i in range(q)]

edges = [[] for i in range(n)]

for a,b,c in data:
    edges[a-1].append([b-1,c])
    edges[b-1].append([a-1,-c])

num = [0 for _ in range(n)]

Ma,mi = 0,0

vi = [False for i in range(n)]
ans = 0

for i in range(n):
    if vi[i]:
        continue
    stack = [i]
    vi[i] = True
    while stack:
        v = stack.pop()
        for e,r in edges[v]:
            if not vi[e]:
                num[e] = num[v] + r
                stack.append(e)
                vi[e] = True

for i in range(n):
    if num[i] < mi:
        mi = num[i]
    elif num[i] > Ma:
        Ma = num[i]
    for e,r in edges[i]:
        if num[i] + r != num[e]:
            ans = -1
            break
    else:
        continue
    break
else:
    print("Yes")
    exit()
print("No")
### BUGGY CODE ###

from collections import deque

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

for i in range(1, N + 1):
    ans.append(A.index(i) + 1)

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

### FIXED CODE ###

from collections import deque

N = int(input())
A = list(map(int, input().split()))
A = list(enumerate(A))
A.sort(key = lambda x: x[1])

ans = deque()

for a in A:
    ans.append(a[0] + 1)

print(" ".join(map(str, ans)))
### BUGGY CODE ###

k, s = map(int, input().split(" "))

count = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split(" "))

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            count += 1

print(count)
### BUGGY CODE ###

import bisect
queue = []
targ = input()
while targ != "end":
    targ = targ.split(' ')
    if targ[0] == "insert":
        queue.insert(bisect.bisect_left(queue,int(targ[1])),int(targ[1]))
    else:
        temp = queue.pop()
        print(temp)
    targ = input()

### FIXED CODE ###

import heapq
queue = []
targ = input()
while targ != "end":
    if targ[0] == "i":
        heapq.heappush(queue,-int(targ.split(' ')[1]))
    else:
        print(-heapq.heappop(queue))
    targ = input()
### BUGGY CODE ###

import numpy as np
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())

ans_array = np.zeros((k, k, k), dtype = np.int)

for i in range(k):
  for j in range(k):
    for h in range(k):
      if ans_array[i, j, h] == 0:
        m_gcd = gcd(i+1, j+1, h+1)
        ans_array[i, j, h] = m_gcd
        if ans_array[i, h, j] == 0:
          ans_array[i, h, j] = m_gcd
        if ans_array[h, j, i] == 0:
          ans_array[h, j, i] = m_gcd

# print(ans_array)
ans = np.sum(ans_array)

print(ans)

### FIXED CODE ###

import math

k = int(input())

ans = 0

for i in range(k):
  for j in range(i,k):
    for h in range(j, k):
      if i == j == h:
        ans += math.gcd(math.gcd(i+1, j+1), h+1)
      elif (i != j) and (j != h) and (i != h):
        ans += math.gcd(math.gcd(i+1, j+1), h+1) * 6
      else:
      	ans += math.gcd(math.gcd(i+1, j+1), h+1) * 3
      
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
N,Q=map(int,input().split())
dg={i:[[],0] for i in range(1,N+1)}
for i in range(1,N):
    a,b=map(int,input().split())
    dg[a][0].append(b)
    dg[b][0].append(a)
#print(dg)
def habatan(p,me):
    if me!=1:
        dg[me][0].remove(p)
    for c in dg[me][0]:
        habatan(me,c)

habatan(0,1)#dg親消し
#print(dg)
#dv={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x=map(int,input().split())
    #dv[p]+=x
    dg[p][1]+=x
#dans={}
def habatan1(p,me):
    if me!=1:
        #dv[me]+=
        dg[me][1]+=dg[p][1]
    #for c in dg[me]:
    for c in dg[me][0]:
        habatan1(me,c)
habatan1(0,1)
for i in range(1,N+1):
    #print(dv[i],end=" ")
    print(dg[i][1],end=" ")
print("")


### FIXED CODE ###

#import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])
### BUGGY CODE ###

def kitai(P):
    kitai = 0
    for i in range(len(P)):
        for j in range(1, P[i]+1):
            kitai += j / P[i]
    return kitai

N, K = map(int, input().split())
P = [int(x) for x in input().split()]
ans = 0
for i in range(K-1, N):
    ans = max(kitai(P[i-K+1:i+1]), ans)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = [int(x) for x in input().split()]
B = [0] * (N+1)
for i in range(1, N+1):
    B[i] = P[i-1] + B[i-1]
ans = 0
for i in range(K, N+1):
    ans = max(ans, B[i] - B[i-K])

print((ans+K)/2)
### BUGGY CODE ###

n,m = map(int,input().split())
li = [[0 for i in range(n)]for j in range(n)]
lis = []

def all_pairs_shortest_paths(W):
    inf = 10**18
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

for _ in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    lis.append((a,b,c))
    li[a][b] = c
    li[b][a] = c

lin = all_pairs_shortest_paths(li)
point = 0

for path in lis:
    a,b,c = path
    flag = False
    for i in range(n):
        for j in range(n):
            if lin[i][a]+c+lin[b][j] == lin[i][j]:
                flag = True
    if not flag:
        point += 1

print(point)

### FIXED CODE ###

n,m = map(int,input().split())
li = [[0 for i in range(n)]for j in range(n)]
lis = []

def all_pairs_shortest_paths(W):
    inf = 10**18
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

for _ in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    lis.append((a,b,c))
    li[a][b] = c
    li[b][a] = c

lin = all_pairs_shortest_paths(li)
point = 0

for path in lis:
    a,b,c = path
    flag = False
    for i in range(n):
        for j in range(n):
            if lin[i][a]+c+lin[b][j] == lin[i][j]:
                flag = True
    if not flag:
        point += 1

print(point)
### BUGGY CODE ###

def main():
	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()))
	d = [0]*x*y
	for i in range(x):
		for j in range(y):
			d[i*y+j] = a[i]+b[j]
	d.sort(reverse=True)
	c.sort(reverse=True)

	c_len = min(k, z)
	d_len = min(k, x*y)
	e = [0]*d_len*c_len
	for i in range(d_len):
		for j in range(c_len):
			e[i*c_len+j] = d[i] + c[j]
	e.sort(reverse=True)
	for i in range(k):
		print(e[i])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	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()))
	d = [0]*x*y
	for i in range(x):
		for j in range(y):
			d[i*y+j] = a[i]+b[j]
	d.sort(reverse=True)
	c.sort(reverse=True)

	c_len = min(k, z)
	d_len = min(k, x*y)
	e = [0]*d_len*c_len
	for i in range(d_len):
		for j in range(c_len):
			e[i*c_len+j] = d[i] + c[j]
	e.sort(reverse=True)
	for i in range(k):
		print(e[i])


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

n = int(input())
s = input()

cnt = []
for i in range(1, n-1):
    if i <= 1:
        a = s[i:].count("E")
    elif i+1 >= n:
        a = s[:i+1].count("W")
    else:
        a = s[:i].count("W")+s[i+1:].count("E")
    cnt.append(a)
print(min(cnt))

### FIXED CODE ###

import numpy as np

n = int(input())
s = input()
s_W = [0]
s_E = []

for i in range(n):
    if s[i] == "W":
        s_W.append(1)
        s_E.append(0)
    else:
        s_W.append(0)
        s_E.append(1)

W_l = np.cumsum(np.array(s_W))
E_l = np.cumsum(np.array(s_E))

ans = []
for j in range(n):
    num = W_l[j]-W_l[0]+E_l[-1]-E_l[j]
    ans.append(num)
print(min(ans))
### BUGGY CODE ###

#https://atcoder.jp/contests/abc072/tasks/arc082_a

from functools import reduce
n = int(input())
l = list(map(int, input().split()))

def get_process(arg):
    def process(accumulator, currentValue):
        if currentValue == arg or currentValue+1 == arg or currentValue-1 == arg:
            return accumulator + 1
        else:
            return accumulator
    return process

def eachX(accumulator, currentValue):
    a = reduce(get_process(currentValue+1), l, 0)
    b = reduce(get_process(currentValue), l, 0)
    c = reduce(get_process(currentValue-1), l, 0)
    if accumulator < max(a, b, c):
        return max(a, b, c)
    else:
        return accumulator

print(reduce(eachX, l, 0))


### FIXED CODE ###

#https://atcoder.jp/contests/abc072/tasks/arc082_a

n = int(input())
l = list(map(int, input().split()))
allx = [0 for _ in range(-1, 10**5+1)]

for value in l:
    allx[value+2] += 1
    allx[value+1] += 1
    allx[value] += 1

print(max(allx))
### BUGGY CODE ###

S=input()
T=input()
a=[None]*26
b=[None]*26
k=1
for i in range(26):
    for j in range(len(S)):
        if S[j]==chr(97+i):
            if a[i]==None:
                a[i]=T[j]
            else:
                if T[j]!=a[i]:
                    k=0
                    break
for i in range(26):
    for j in range(len(S)):
        if T[j]==chr(97+i):
            if b[i]==None:
                b[i]=S[j]
            else:
                if S[j]!=b[i]:
                    k=0
                    break
if k==1:print("Yes")
else:print("No")  

### FIXED CODE ###

S=input()
T=input()
a=[None]*26
b=[None]*26
k=1
for i in range(26):
    for j in range(len(S)):
        if S[j]==chr(97+i):
            if a[i]==None:
                a[i]=T[j]
            else:
                if T[j]!=a[i]:
                    k=0
                    break
for i in range(26):
    for j in range(len(S)):
        if T[j]==chr(97+i):
            if b[i]==None:
                b[i]=S[j]
            else:
                if S[j]!=b[i]:
                    k=0
                    break
if k==1:print("Yes")
else:print("No")
### BUGGY CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=[[[0,0] for i in range(w)] for j in range(h)]
for i in range(h):
    k=0
    while k<w:
        cnt=0
        if s[i][k]==".":
            j=k
            while k<w and s[i][k]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                a[i][x][0]=cnt
        else:
            k+=1
for i in range(w):
    k=0
    while k<h:
        cnt=0
        if s[k][i]==".":
            j=k
            while k<h and s[k][i]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                a[x][i][1]=cnt
        else:
            k+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,a[i][j][0]+a[i][j][1])
print(ans-1)


### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=[[0]*w for j in range(h)]
b=[[0]*w for j in range(h)]
for i in range(h):
    k=0
    rep=0
    while k<w:
        cnt=0
        if s[i][k]==".":
            j=k
            while k<w and s[i][k]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                a[i][x]=cnt
        else:
            k+=1
for i in range(w):
    k=0
    while k<h:
        cnt=0
        if s[k][i]==".":
            j=k
            while k<h and s[k][i]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                b[x][i]=cnt
        else:
            k+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,a[i][j]+b[i][j])
print(ans-1)
### BUGGY CODE ###

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

ans = 0

for i in range(0, len(P)-1):
    if (P[1] <= P[0]):
        ans += 1
        del(P[0])
    else:
        del(P[1])

print(ans+1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = 0
pivot = P[0]

for i in range(0, len(P)):
    if (pivot >= P[i]):
        ans += 1
        pivot = P[i]

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

#import itertools
import math
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
k = 0
j = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        j = dic2[a[i]][0]
        k = i

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = n + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#a = cmb(10**9,80,mod)

for i in range(n + 1):
    if i == 0:
        print(n)
    else:
        if j + n - k >= i:
            print((combinations_count(n + 1, i + 1) - combinations_count(j + n - k, i)) % mod)
        else:
            print(cmb(n + 1, i + 1, mod))

### FIXED CODE ###

#import itertools
import math
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
k = 0
j = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        j = dic2[a[i]][0]
        k = i

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = n + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(n + 1):
    if i == 0:
        print(n)
    else:
        if j + n - k >= i:
            if (cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod)) >= 0:
                print(cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod))
            else:
                print(cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod) + mod)
        else:
            print(cmb(n + 1, i + 1, mod))
### BUGGY CODE ###

from heapq import heappop, heappush
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

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

pq = []
for i in range(N):
    heappush(pq, (-A[i] * F[i], F[i]))
    
for _ in range(K):
    c, u = heappop(pq)
    heappush(pq, (c + u, u))
    
print(max(0, -min(v for v, _ in pq)))




### FIXED CODE ###

from heapq import heappop, heappush
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

def ok(x):
    cnt = 0
    for i in range(N):
        current = A[i] * F[i]
        if current > x:
            cnt += -(-(current - x) // F[i])
            
    return cnt <= K

A.sort()
F.sort(reverse=True)
lb = 0
ub = 10 ** 12 + 1

while ub - lb > 1:
    mid = (lb + ub) // 2
    
    if ok(mid):
        ub = mid
    else:
        lb = mid
        
if sum(A) <= K:
    print(0)
else:
    print(ub)
### BUGGY CODE ###

n = int(input())
s = [sorted(list(input())) for _ in range(n)]

ans = 0
for i in range(n):
   for j in range(i+1, n):
      if s[i] == s[j]:
         ans += 1

print(ans)


### FIXED CODE ###

import collections

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]

c = collections.Counter(s)

ans = 0
for i in set(s):
   n = c[i]
   ans += n * (n - 1) // 2

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

Q, H, S, D = map(int, input().split())
N = int(input())

p025 = Q
p05 = min(H, p025 * 2)
p1 = min(S, p05 * 2)
p2 = min(D, p1 * 2)

ans = 0
while N > 0:
    if N >= 2:
        N -= 2
        ans += p2
    elif N >= 1:
        N -= 1
        ans += p1

print(ans)


### FIXED CODE ###

Q, H, S, D = map(int, input().split())
N = int(input())

p025 = Q
p05 = min(H, p025 * 2)
p1 = min(S, p05 * 2)
p2 = min(D, p1 * 2)

ans = 0
if N % 2 != 0:
    N -= 1
    ans += p1
ans += (N // 2) * p2

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

N = int(input())
P = list(map(int,input().split()))
num = 1
for i in range(1,N):
    flag = 0
    min_i = min(P[:i])
    if min_i >= P[i]:
        num += 1
print(num)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
num = 1
min_P = P[0]
for i in range(1,N):
    if P[i] < min_P:
        min_P = P[i]
        num += 1
print(num)
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
A = []
black = []
for i in range(H):
    A.append(list(input()))
    for j in range(W):
        if A[i][j] == '#':
            black.append([i,j])

counter = len(black)
dist = 0
cur_black = copy.deepcopy(black)
next_black = copy.deepcopy(black)
while True:
    if counter == W * H:
        break
    dist += 1
    black = copy.deepcopy(next_black)
    next_black = []
    for b in black:
        if b[0] != 0 and [b[0] - 1, b[1]] not in cur_black:
            cur_black.append([b[0] - 1, b[1]])
            next_black.append([b[0] - 1, b[1]])
            counter += 1
        if b[1] != 0 and [b[0], b[1] - 1] not in cur_black:
            cur_black.append([b[0], b[1] - 1])
            next_black.append([b[0], b[1] -1])
            counter += 1
        if b[0] != H - 1 and [b[0] + 1, b[1]] not in cur_black:
            cur_black.append([b[0] + 1, b[1]])
            next_black.append([b[0] + 1, b[1]])
            counter += 1
        if b[1] != W - 1 and [b[0], b[1] + 1] not in cur_black:
            cur_black.append([b[0], b[1] + 1])
            next_black.append([b[0], b[1] + 1])
            counter += 1            
print(dist)

### FIXED CODE ###

H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)