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

from sys import stdin,stdout


def knapsack(i,w):
    if dp[i][w]!=-1:
        return dp[i][w]
    else:
        if w-wi[i]>=0:
            dp[i][w] = max(knapsack(i-1,w-wi[i])+v[i],knapsack(i-1,w))
        else:
            dp[i][w] = knapsack(i-1,w)
        return dp[i][w]
n,w= map(int,input().split())
wi=[0]
v=[0]
for i in range(n):
    x,y= map(int,stdin.readline().split())

    wi.append(x)
    v.append(y)
dp = [[-1 for i in range(w+1)] for j in range(n+1)]
for i in range(w+1):
    dp[0][i]=0
for j in range(n+1):
    dp[j][0]=0
stdout.write(str(knapsack(n,w)) + "\n")
#print(dp)

### FIXED CODE ###

N,W=map(int,input().split())
dp=[-1]*(W+1)
dp[0]=0
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(W+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i+w],dp[i]+v)
print(max(dp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#import fractions #fractions.gcd() python~3.4
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
A = list(map(int, input().split()))
INF = 1e+10
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7 
    if x == 9:
        return 6

A.sort(reverse=True)

dp=[-INF]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(M):
        if i-f(A[j]) >= 0:
            dp[i] = max(dp[i],dp[i-f(A[j])]+1)
 
ans = ""
remain = dp[N]
match = N

while match > 0:
    for i in range(M):
        if match - f(A[i]) >0 and dp[match - f(A[i])] == remain - 1:
            ans += str(A[i])
            match -= f(A[i])
            remain -= 1
            
            break
            
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

#import fractions #fractions.gcd() python~3.4
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
A = list(map(int, input().split()))
INF = 1e+10
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7 
    if x == 9:
        return 6

A.sort(reverse=True)

dp=[-INF]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(M):
        if i-f(A[j]) >= 0:
            dp[i] = max(dp[i],dp[i-f(A[j])]+1)
 
ans = ""
remain = dp[N]
match = N

while match > 0:
    for i in range(M):
        if match - f(A[i]) >=0 and dp[match - f(A[i])] == remain - 1:
            ans += str(A[i])
            match -= f(A[i])
            remain -= 1
            
            break
            
print(ans)
### BUGGY CODE ###

from collections import defaultdict

s = input()
x, y = map(int, input().split())

d = [len(x) for x in s.split('T')]

dx = d[0::2]
dpx = [defaultdict(bool) for _ in range(len(dx) + 1)]
dpx[0][0] = True
max_x = sum(dx)
for i in range(len(dx)):
    for j in range(-max_x, max_x + 1):
        if i == 0:
            dpx[i + 1][j] = dpx[i][j - dx[i]]
        else:
            dpx[i + 1][j] = dpx[i][j - dx[i]] or dpx[i][j + dx[i]]

dy = d[1::2]
dpy = [defaultdict(bool) for _ in range(len(dy) + 1)]
dpy[0][0] = True
max_y = sum(dy)
for i in range(len(dy)):
    for j in range(-max_y, max_y + 1):
        dpy[i + 1][j] = dpy[i][j - dy[i]] or dpy[i][j + dy[i]]

if dpx[-1][x] and dpy[-1][y]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict

s = input()
x, y = map(int, input().split())

d = [len(x) for x in s.split('T')]

dx = d[0::2]
n_dx = len(dx)
dp = {0}
for i in range(n_dx):
    tmp = set()
    for j in dp:
        if i == 0:
            tmp.add(j + dx[i])
        else:
            tmp.add(j - dx[i])
            tmp.add(j + dx[i])
    dp = tmp
x_flag = x in dp

dy = d[1::2]
n_dy = len(dy)
dp = {0}
for i in range(n_dy):
    tmp = set()
    for j in dp:
        tmp.add(j - dy[i])
        tmp.add(j + dy[i])
    dp = tmp
y_flag = y in dp

if x_flag and y_flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
t = []
mod = (10 ** 9) + 7
count = 0
while sum(a) > 0:
    t.append(sum([1 & i for i in a]))
    a = [i >> 1 for i in a]
    count += 1
ans = 0
for i, j in zip(t, range(count)):
    ans += i * (n - i) * (2 ** j)
    ans = ans % mod
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = (10 ** 9) + 7
max_a = max(a)
ans = 0
for j in range(len(bin(max(a))) - 2):
    t = sum([1 & i for i in a]) 
    ans += (2 ** j) * t * (n - t)
    a = [i >> 1 for i in a]
    ans = ans % mod
print(ans)
### BUGGY CODE ###

n= int(input())
cnt = 1
for i in range(1,n+1):
  cnt *= i
print(cnt%(10**9+7))

### FIXED CODE ###

n= int(input())
cnt = 1
for i in range(1,n+1):
  cnt *= i
  cnt %= (10**9+7)
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
check = list(set(A))
num = 0
for c in check:
  cnt = A.count(c)
  if c < cnt:
    num += abs(cnt- c)
  elif c > cnt:
    num += cnt
print(num)

### FIXED CODE ###

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

d = {}
for i in range(N):
  if(a[i] not in d):
    d[a[i]] = 1
  else:
    d[a[i]] += 1
cnt = 0
for k, v in d.items():
  if(k > v):
    cnt += v
  elif(k < v):
    cnt += v - k
print(cnt)
### BUGGY CODE ###

H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
fac = [1 for _ in range(10**6+1)]
for i in range(1, 10 **6):
    fac[i+1] = fac[i] * (i + 1)

def combination(n, r):
    result = fac[n] // (fac[r] * fac[n-r])
    return result

for i in range(B, W):
    ans += (combination(H - A - 1 + i, i) * combination(A - 1 + W - i - 1, W - i -1))
    ans %= mod
print(ans)


### FIXED CODE ###

H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
X = [i for i in range(H + W + 1)]
X[0] = 1
for i in range(2, H + W + 1):
    X[i] = X[i - 1] * i % mod
Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod


def combination(x, y):
    return X[x] * Y[y] * Y[x - y] % mod


for i in range(B, W):
    ans += (combination(H - A - 1 + i, i) * combination(A - 1 + W - i - 1, W - i -1))
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
n = INT()
a = LIST()
b = []

for i in range(1, n+1):
	b.append(a[i-1])
	b.reverse()

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

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

n = INT()
a = LIST()
a_front = []
a_back = []
 
flg = 1
for i in range(n):
	if flg == 1:
		a_back.append(a[i])
	else:
		a_front.append(a[i])
	flg *= -1

ans = a_front[::-1] + a_back
if flg == 1:
	print(*ans)
else:
	print(*ans[::-1])
### BUGGY CODE ###

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort(key = lambda x:x[1], reverse = True)
day = {i+1 for i in range(M)}
ans = 0
for i in range(N):
    check = {a[i][0] + j for j in range(N)}
    if check & day:
        ans += a[i][1]
        day -= {min(check & day)}
print(ans)

### FIXED CODE ###

import heapq as hq
import numpy as np

N, M = map(int, input().split())
job = [list(map(int, input().split())) for _ in range(N)]
ans = 0
job.sort()
job.append([np.inf, np.inf])
jobhq = []
index = 0
for day in range(1, M + 1):
    while day >= job[index][0]:
        hq.heappush(jobhq, - job[index][1])
        index += 1
    if jobhq:
        ans += - hq.heappop(jobhq)
print(ans)
### BUGGY CODE ###

N = int(raw_input())
S = list(raw_input())

ans = N
for i in range(N):
    left = S[:i].count('W')
    right = S[i:].count('E')
    ans = min(ans, left+right)

print(ans)

### FIXED CODE ###

N = int(raw_input())
S = list(raw_input())

ans = N
min_ans = N
for i in range(N):
    if i == 0:
        ans = S[1:].count('E')
        min_ans = ans
    else:
        if S[i-1] == 'W':
            ans += 1
        if S[i] == 'E':
            ans -= 1
        min_ans = min(min_ans, ans)

print(min_ans)
### BUGGY CODE ###

N, Q = map(int, input().split(" "))
S = input()
for _ in range(Q):
    l, r = map(int, input().split(" "))
    s = S[l-1:r]
    len_ss = 0
    for i in s.split("AC"):
        len_ss += len(i)
    print(int((len(s)-len_ss)/2))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
S = input()
t = [0] * (N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
for i in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

# -*- coding:utf-8 -*-
# /usr/bin/python3


def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      top.sort()
      if len(top) > a-k:
        s += sum(top[-(a-k):])
        del top[-(a-k):]
      else:
        s += sum(top)
        top = []
      k = a

    top.append(b)


  top.sort()
  s += sum(top[-(m-k+1):])
  print(s)

if __name__=='__main__':
  main()


### FIXED CODE ###

# -*- coding:utf-8 -*-
# /usr/bin/python3

from heapq import heappush, heappop

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      s += (-sum([heappop(top) for _ in range(a-k) if len(top) != 0]))
      k = a
    heappush(top, -b)

  s += (-sum([heappop(top) for _ in range(m-k+1) if len(top) != 0]))
  print(s)

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

from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]

d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(1,k+1):
        if 0 <= bx+i < he and l[bx+i][by] != "@":
            if d[bx+i][by] > dis+1:
                d[bx+i][by] = dis+1
                q.append((dis+1,bx+i,by))
        else:
            break
    for i in range(1,k+1):
        if 0 <= bx-i < he and l[bx-i][by] != "@":
            if d[bx-i][by] > dis+1:
                d[bx-i][by] = dis+1
                q.append((dis+1,bx-i,by))
        else:
            break
    for i in range(1,k+1):
        if 0 <= by+i < w and l[bx][by+i] != "@":
            if d[bx][by+i] > dis+1:
                d[bx][by+i] = dis+1
                q.append((dis+1,bx,by+i))
        else:
            break
    for i in range(1,k+1):
        if 0 <= by-i < w and l[bx][by-i] != "@":
            if d[bx][by-i] > dis+1:
                d[bx][by-i] = dis+1
                q.append((dis+1,bx,by-i))
        else:
            break

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])

### FIXED CODE ###

from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(4):
        for j in range(1,k+1):
            nx = bx+dx[i]*j
            ny = by+dy[i]*j
            if 0 > nx or 0 > ny or nx >= he  or ny >= w:
                break
            if l[nx][ny] == "@":
                break
            if d[nx][ny] <= dis:
                break
            if d[nx][ny] > dis+1:
                d[nx][ny] = dis+1
                q.append((dis+1,nx,ny))

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]

# Create the pascal triangle
pascal = [[0 for i in range(j+1)] for j in range(4001)]
pascal[0][0] = 1
for i in range(4000):
    for j in range(i+1):
        pascal[i+1][j] += pascal[i][j]
        pascal[i+1][j+1] += pascal[i][j]


class Mod(object):
    def __init__(self, base):
        self.base = base
        self.x = 0

    def add(self, y):
        self.x += y % self.base
        self.x %= self.base

    def sub(self, y):
        self.x -= y % self.base
        self.x %= self.base

    def mul(self, y):
        self.x *= y % self.base
        self.x %= self.base


def comb(x, y):
    if x <= 0 or y < 0 or x < y:
        return 0
    return pascal[x][y]


def f2(x, y):
    return comb(x+y-1, y-1)


def f(x, y):
    return f2(x-y, y)


if __name__ == "__main__":
    BASE = int(1e+9 + 7)
    for i in range(1, k+1):
        count = Mod(BASE)
        count.add(f(k, i) * f(n-k, i-1))
        count.add(f(k, i) * f(n-k, i))
        count.add(f(k, i) * f(n-k, i))
        count.add(f(k, i) * f(n-k, i+1))
        print(count.x)

### FIXED CODE ###

n, k = [int(i) for i in input().split()]

# Create the pascal triangle
pascal = [[0 for i in range(j+1)] for j in range(2001)]
pascal[0][0] = 1
for i in range(2000):
    for j in range(i+1):
        pascal[i+1][j] += pascal[i][j]
        pascal[i+1][j+1] += pascal[i][j]


class Mod(object):
    def __init__(self, base):
        self.base = base
        self.x = 0

    def add(self, y):
        self.x += y % self.base
        self.x %= self.base

    def sub(self, y):
        self.x -= y % self.base
        self.x %= self.base

    def mul(self, y):
        self.x *= y % self.base
        self.x %= self.base


def comb(x, y):
    if x < y or (x == 0 and y != 0) or y < 0:
        return 0
    return pascal[x][y]


def f2(x, y):
    return comb(x+y-1, y-1)


def f(x, y):
    if x == 0 and y == 0:
        return 1
    return f2(x-y, y)


if __name__ == "__main__":
    BASE = int(1e+9 + 7)
    for i in range(1, k+1):
        count = Mod(BASE)
        count.add(f(k, i) * f(n-k, i-1))
        count.add(f(k, i) * f(n-k, i))
        count.add(f(k, i) * f(n-k, i))
        count.add(f(k, i) * f(n-k, i+1))
        print(count.x)
### BUGGY CODE ###

def main():
    from collections import deque

    INF = float('inf')

    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())
    S = [input() for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            ti = t[i]
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if ti[j] <= a + 1:
                    continue
                ti[j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


### FIXED CODE ###

from collections import deque

INF = float('inf')

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())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

n,m,l = map(int, input().split())
INF = 1001001001
dist = [[INF for i in range(n)] for i in range(n)]
#make graph
for i in range(n):
  dist[i][i] = 0
for i in range(m):
  a, b, c = map(int, input().split())
  dist[a-1][b-1] = dist[b-1][a-1] = c
#warshall-froyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
dist2 =  [[INF for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dist[i][j] <=l:
      dist2[i][j] = 1
#warshall-froyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist2[i][j] = min(dist2[i][j], dist2[i][k]+dist2[k][j])
q = int(input())
for i in range(q):
  s,t = map(int, input().split())
  if dist2[s-1][t-1] == INF:
    print(-1)
  else:
    print(dist2[s-1][t-1]-1)

### FIXED CODE ###

n,m,l = map(int, input().split())
INF = 1001001001
dist = [[INF for i in range(n)] for i in range(n)]
#make graph
for i in range(n):
  dist[i][i] = 0
for i in range(m):
  a, b, c = map(int, input().split())
  dist[a-1][b-1] = dist[b-1][a-1] = c
#warshall-froyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
dist2 =  [[INF for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dist[i][j] <=l:
      dist2[i][j] = 1
#warshall-froyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist2[i][j] = min(dist2[i][j], dist2[i][k]+dist2[k][j])
q = int(input())
for i in range(q):
  s,t = map(int, input().split())
  if dist2[s-1][t-1] == INF:
    print(-1)
  else:
    print(dist2[s-1][t-1]-1)
### BUGGY CODE ###

inp1 = input().split()
inp2 = input().split()
a = int(inp1[0])
b = inp2
b = [int(s) for s in inp2]
ansno = a
#print("b: ",b)
#print("b[:3] ",b[:3])
#print("b[:0] ",b[:0])
ii = 0
#print("b[:ii+1] ",b[:ii+1])
for i in b:
  if i ==0:
    continue
#  print(i)
  jj = 0
  for j in b[:ii]:
    if i >= j:
#      print(i, ">=", j,"break")
      ansno -= 1
#      print("ansno: ",ansno)
      break
    else:
      jj+=1
  ii+=1
#print("final ansno: ",ansno)
print(ansno)
      
    

### FIXED CODE ###

n = int(input())
m = input().split()
ppp = list(map(int, m))
max = 2*10**5+1
ans = 0
for p in ppp:
    if p < max:
        ans += 1
        max = p
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    answer = 1
    for aa in a:
        answer *= aa
    if answer > 10 ** 18:
        print(-1)
    else:
        print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_val = pow(10, 18)
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
            if max_val < answer:
                print(-1)
                break
        else:
            print(answer)


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

import math
import time
import pprint
import sys
from queue import Queue
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while q.qsize() != 0:
        tmp_y, tmp_x = q.get()
        for i in range(4):
            if ( 0 <= tmp_x + x_diff[i] <= w-1 
                    and 0 <= tmp_y + y_diff[i] <= h-1 
                    and check[tmp_y + y_diff[i]][tmp_x + x_diff[i]] == 0 
                    and a[tmp_y + y_diff[i]][tmp_x + x_diff[i]] != '#'):
                check[tmp_y + y_diff[i]][tmp_x + x_diff[i]] = 1 
                require[tmp_y + y_diff[i]][tmp_x + x_diff[i]] = require[tmp_y][tmp_x] + 1
                q.put([tmp_y + y_diff[i], tmp_x + x_diff[i]])
    return require


h, w = MI()
a = [IS() for _ in range(h)]
out = 0
queue = Queue()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            queue.put([i,j])

ans = bfs(queue)

for i in range(h):
    for j in range(w):
        out = max(out,ans[i][j])

print(out)


### FIXED CODE ###

import math
import time
import pprint
import sys
from collections import deque
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while len(q) != 0:
        tmp_y, tmp_x = q.popleft()
        # print(tmp_y, tmp_x)
        for i in range(4):
            next_y = tmp_y + y_diff[i]
            next_x = tmp_x + x_diff[i]
            if ( 0 <= next_x <= w-1 
                    and 0 <= next_y <= h-1 
                    and check[next_y][next_x] == 0 
                    and a[next_y][next_x] != '#'):
                check[next_y][next_x] = 1 
                require[next_y][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])
                # pp.pprint(check)
    return require


h, w = MI()
a = [IS() for _ in range(h)]
# start = time.time()
# h, w = 1000, 1000
# a = ['#.#.' * (w//4) for _ in range(h)]
out = 0
que = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append([i,j])
# print(que)

ans = bfs(que)

for i in range(h):
    for j in range(w):
        out = max(out,ans[i][j])

# print(time.time() - start)
print(out)