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

import collections
import math

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M=map(int, input().split())
l=[[0 for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    l[a-1][b-1]=1


a = np.array(l)

n, labels = connected_components(a)

cc=collections.Counter(labels)
ans=max(cc.values())
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            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

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    A,B=map(int,input().split())
    uf.union(A-1,B-1)
ans=0
for i in range(N):
    ans=max(ans,uf.size(i))

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

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    lis = list(map(int, input().split()))
    ans = 0

    for i in range(n):
        for j in range(max(i,lis[i]), n):
            if lis[i] + lis[j] == j - i:
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

n = int(input())
lis = list(map(int, input().split()))

L = []
R = []
for i, j in enumerate(lis):
    L.append(i+j)
for i, j in enumerate(lis):
    R.append(i-j)
    
ref = dict(Counter(R))
ans = 0
for i in L:
    ans += ref.get(i, 0)
print(ans)
### BUGGY CODE ###

import numpy as np
# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
#B =np.zeros(N)
A =np.array(A,dtype=np.int64)
#
l =0
r =N
for j in range(K):
    B =np.zeros(N,dtype=np.int64)
    for i in range(N):
        index =A[i]
        if i-index <0:
            l=0
        else:
            l =i -index
        if i +index >N:
            r =N 
        else:
            r =i +index +1
        B[l:r] +=1 
        if np.all(B >=N):
            break
    A =B
    
print(*B)

### FIXED CODE ###

# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# 
    
# 初期入力
    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
    
    
l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)
### BUGGY CODE ###

from collections import deque,Counter
N,T=map(int, raw_input().split())
A=map(int, raw_input().split())

q=deque( sorted(A, key=lambda x: x,reverse=True) )


b=[]
for i in range(N-1):
	q.remove(A[i])
	max_n=q[0]
	b.append(max_n-A[i])

C=Counter(b)
max_key=max(C.keys())

print C[max_key]

### FIXED CODE ###

from collections import Counter
N,T=map(int, raw_input().split())
A=map(int, raw_input().split())

A_r=[None for i in range(N)]
n=0
for i in range(N-1,-1,-1):
	n=max(A[i],n)
	A_r[i]=n

B=[]
for i in range(N-1):
	B.append(A_r[i+1]-A[i])


C=Counter(B)

print C[max(B)]
### BUGGY CODE ###

import itertools
from sys import stdin
N=int(input())
st=list(stdin.readline().strip())
count=0
cnt=0
# stt=set(st)
# stt=list(stt)
num=["0","1","2","3","4","5","6","7","8","9"]
#num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break
    cnt = 0

print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

K = int(input())

ans = 0

import math

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

### FIXED CODE ###

K = int(input())

ans = 0
ans2 = 0


import math

for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            tmp = math.gcd(i,j)
            ans += math.gcd(tmp,k)
            
for i in range(1,K+1):
    for j in range(i+1,K+1):
        for k in range(j+1,K+1):
            tmp3 = math.gcd(i,j)
            ans2 += math.gcd(tmp3,k)
      
tmp2 = 0

for i in range(1,K+1):
    tmp2 += i
    
print((ans - tmp2 - ans2)*3 + ans2*6 + tmp2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  b.append(str(a.index(i+1) + 1))
b=' '.join(b)  
print(b)



### FIXED CODE ###

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

ans = [0 for i in range(n)]
for i, name in enumerate(a):
    ans[name-1] = i+1
print(*ans)
### BUGGY CODE ###

s = input()
s2= list(s)
if s2==s2[::-1]:
  print(0)
  exit()
s1 = []
le = []
lex = []
cnt= 0
for i in list(s):
  if i!="x":
    le.append(cnt)
    s1.append(i)
  else:
    lex.append(cnt)
  cnt+=1
if s1!=s1[::-1]:
  print(-1)
  exit()
ans = []
res=0
if len(le)%2==1:
  midlle=le[len(le)//2]
  for i in lex:
    if not i-midlle in ans:
      res+=1
      ans.append(abs(i-midlle))
    else:
      res-=1
  print(res)
else:
  midlle=(le[len(le)//2]+le[len(le)//2-1])//2
  for i in lex:
    if not i-midlle in ans:
      if i-midlle==0:
        continue
      res+=1
      ans.append(abs(i-midlle))
    else:
      res-=1
  print(res)

### FIXED CODE ###

s = list(input())
s1=s[::-1]
ans = 0
cnt = 0
cnt1 = 0
while cnt<len(s) and cnt1<len(s) and cnt<=len(s)-1-cnt1:
  if s[cnt]!=s1[cnt1]:
    if s[cnt]=="x" and s1[cnt1]!="x":
      cnt+=1
      ans+=1
    elif s1[cnt1]=="x" and s[cnt]!="x":
      cnt1+=1
      ans+=1
    elif s[cnt]!="x" and s1[cnt1]!="x":
      print(-1)
      exit()
  elif s[cnt]==s1[cnt1]:
    cnt+=1
    cnt1+=1
print(ans)
### BUGGY CODE ###

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

def calc_gcd_list(l):
    gcd = l[0]
    for i in range(1, N):
        gcd = gcd(gcd, l[i])
    return gcd

def calc_lcm_list(l):
    lcm = l[0]
    for i in range(1, N):
        lcm = lcm * l[i] // gcd(lcm, l[i])
    return lcm


N = input_one_number()
lstA = input_multiple_number_as_list()
lcm = calc_lcm_list(lstA)
pow = 10**9 +7
print(sum(lcm//a for a in lstA)%pow)


### FIXED CODE ###

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

def calc_gcd_list(l):
    gcd = l[0]
    for i in range(1, N):
        gcd = gcd(gcd, l[i])
    return gcd

def calc_lcm_list(l):
    lcm = 1
    for i in l:
        lcm = lcm * i // gcd(lcm, i)
    return lcm


N = input_one_number()
lstA = input_multiple_number_as_list()
lcm = calc_lcm_list(lstA)
pow = 10**9 +7
print(sum(lcm//a for a in lstA)%pow)
### BUGGY CODE ###

def solve():
    s = input()
    t = input()
    s_size = len(s)
    t_size = len(t)
    dp = ["" for i in range(s_size+1)]
    for i in range(1, t_size+1):
        tmp = ""
        for j in range(1, s_size+1):
            tmp1 = dp[j]
            if t[i-1] == s[j-1]:
                dp[j] = tmp + t[i-1]
            else:
                dp[j] = dp[j-1] if len(dp[j-1]) > len(tmp1) else tmp1
            tmp = tmp1
    print(dp[-1])
solve()

### FIXED CODE ###

def solve():
    s = input()
    t = input()
    s_size = len(s)
    t_size = len(t)
    dp = [[0 for i in range(s_size+1)] for j in range(t_size+1)]
    for i in range(1, t_size+1):
        for j in range(1, s_size+1):
            if t[i-1] == s[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    ans = ""
    i, j = t_size, s_size
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            ans = t[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
solve()
### BUGGY CODE ###

from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append('#' * (W+2))
    for h in range(H):
        s = '#' + input() + '#'
        S.append(s)
    S.append('#' * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in dirs:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for i, j in product(range(1, H+1), range(1, W+1)):
        if S[i][j] == '.':
            d = bfs(i, j, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

# -*- coding: utf-8 -*-
S = input()
dict_amari = {}
count = 0

def amari_new(dict_amari, s):
  dict_amari_new = {(10*k+s)%2019 : v for k,v in dict_amari.items()}
  if s in dict_amari_new.keys():
    dict_amari_new[s] += 1
  else:
    dict_amari_new[s] = 1
  return dict_amari_new

for s in S:
  dict_amari = amari_new(dict_amari, int(s))
  if 0 in dict_amari.keys():
    count += dict_amari[0]

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = input()
list_amari = [0 for i in range(2019)]
amari_prev = 0
X = 1

for i in range(len(S)):
  amari = (int(S[-i-1])*X+amari_prev)%2019
  list_amari[amari] += 1
  amari_prev = amari
  X = (10*X)%2019

count = list_amari[0]
for v in list_amari:
  count += v*(v-1)//2

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

n, kosuu = map(int, input().split(" "))
a=list(map(int, input().split(" ")))
temp = []
for i in range(n - kosuu + 1):
  temp.append(sum(a[i:i+kosuu]))
print((max(temp) + kosuu) / 2)

### FIXED CODE ###

n, kosuu = map(int, input().split(" "))
a=list(map(int, input().split(" ")))
first = sum(a[:kosuu])
temp = []
temp.append(first)
for i in range(n - kosuu):
  first = first + a[i + kosuu] - a[i]
  temp.append(first)
print((max(temp) + kosuu) / 2)
### BUGGY CODE ###

def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
s_mid = [int(input()) for i in range(a)]
s.extend(s_mid)
s.append(10**18)

t = [-10**18]
t_mid = [int(input()) for i in range(b)]
t.extend(t_mid)
t.append(10**18)

for i in range(q):
  x = int(input())
  si = find_min_fuka_idx(s, x)
  tj = find_min_fuka_idx(t, x)
  print(min(abs(x-s[si])+abs(s[si]-t[tj]),\
            abs(x-s[si])+abs(s[si]-t[tj-1]),\
           abs(x-t[tj])+abs(t[tj]-s[si]),\
            abs(x-t[tj])+abs(t[tj]-s[si-1]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj-1]),\
           abs(x-t[tj-1])+abs(t[tj-1]-s[si]),\
            abs(x-t[tj-1])+abs(t[tj-1]-s[si-1])))


### FIXED CODE ###

import bisect
def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
s_mid = [int(input()) for i in range(a)]
s.extend(s_mid)
s.append(10**18)

t = [-10**18]
t_mid = [int(input()) for i in range(b)]
t.extend(t_mid)
t.append(10**18)

for i in range(q):
  x = int(input())
  si = bisect.bisect_right(s, x)
  tj = bisect.bisect_right(t, x)
  print(min(abs(x-s[si])+abs(s[si]-t[tj]),\
            abs(x-s[si])+abs(s[si]-t[tj-1]),\
           abs(x-t[tj])+abs(t[tj]-s[si]),\
            abs(x-t[tj])+abs(t[tj]-s[si-1]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj-1]),\
           abs(x-t[tj-1])+abs(t[tj-1]-s[si]),\
            abs(x-t[tj-1])+abs(t[tj-1]-s[si-1])))
### BUGGY CODE ###

K,S = (int(_) for _ in input().split())

out = 0

for x in range(K+1):
    for y in range(x+1):
        for z in range(y+1):
            if x + y + z == S :
                if x == y and y == z :
                    out += 1
                elif x == y or y == z or z == x:
                    out += 3
                else:
                    out += 6

print(out)


### FIXED CODE ###

def binary_search_list(beSearched,wanted) :
    l = 0
    r = len(beSearched)

    #print("condition = {}".format(r-l))

    while r - l >= 1 :
        s = (l + r) // 2
        #print("l={} r={} s={}".format(l,r,s))
        if beSearched[s] == wanted :
            return True
        if beSearched[s] > wanted :
            r = s
        else :
            l = s + 1

    return False

K,S = (int(_) for _ in input().split())
num = [_ for _ in range(K+1)]
out = 0
for i in range(K+1):
    for j in range(i+1):
        if 0 <= S - i - j <= j :
            if i == j and j == S - i - j:
                out += 1
            elif i == j or j == S - i - j or S -i - j == i:
                out += 3
            else :
                out += 6
        #print(num[:j+1])
        #b = binary_search_list(num[:j+1],S - i - j)
        #print("b={} i={} j={} k = {}".format(b,i,j, S- i -j))
        #if b :
            #if i == j and j == S - i - j:
                #out += 1
            #elif i == j or j == S - i - j or S -i - j == i:
                #out += 3
            #else :
                #out += 6

print(out)
### BUGGY CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = 1

    for i in range(N):
        prev_tmp = tmp
        tmp *= A[i]

        if i > K - 1:
            tmp //= A[i-K]

            if tmp > prev_tmp:
                print('Yes')
            else:
                print('No')

if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(N-K):
        if A[i] < A[i+K]:
            print('Yes')
        else:
            print('No')

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

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

# pascal = [[] for _ in range(4005)]

pascal_triangle = [
    [0 for _ in range(1 + i)] for i in range(4005)
    # [0 for _ in range(1 + i)] for i in range(10)
]

def init():
    pascal_triangle[0][0] = 1
    for i in range(1, len(pascal_triangle)):
        for j in range(len(pascal_triangle[i])):
            new_value = 0
            if j < len(pascal_triangle[i-1]):
                new_value += pascal_triangle[i-1][j]
            if 0 <= j - 1:
                new_value += pascal_triangle[i-1][j-1]
            pascal_triangle[i][j] = new_value


# x 個の玉を y グループに分ける場合の数 (1個以上の玉のグループ)
def f2(x, y):
    return pascal_triangle[x + y - 1][y - 1]


# x 個の玉を y グループに分ける場合の数 (0個以上の玉のグループ)
def f(x, y):
    if x < y:
        return 0
    if x == 0 and y == 0:
        return 1
    if x == 0:
        return 0
    if y == 0:
        return 0
    return f2(x - y, y)


init()

# N = 5, K = 3
N, K = list(map(int, input().split()))

for i in range(1, K + 1):
    result = f(K, i) * (
        f(N - K, i - 1) +
        f(N - K, i) +
        f(N - K, i) +
        f(N - K, i + 1)
    )
    # print('0', i)
    # print('1', f(K, i))
    # print('2', f(N - K, i - 1))
    # print('3', f(N - K, i))
    # print('4', f(N - K, i + 1))
    print(result % 1000000007)
    # print("")

# for line in pascal_triangle:
#     print(line)

### FIXED CODE ###

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

import math

# pascal = [[] for _ in range(4005)]

# pascal_triangle = [
#     [0 for _ in range(1 + i)] for i in range(4005)
#     # [0 for _ in range(1 + i)] for i in range(10)
# ]

def init():
    # pascal_triangle[0][0] = 1
    # for i in range(1, len(pascal_triangle)):
    #     for j in range(len(pascal_triangle[i])):
    #         new_value = 0
    #         if j < len(pascal_triangle[i-1]):
    #             new_value += pascal_triangle[i-1][j]
    #         if 0 <= j - 1:
    #             new_value += pascal_triangle[i-1][j-1]
    #         pascal_triangle[i][j] = new_value
    pass


# x 個の玉を y グループに分ける場合の数 (1個以上の玉のグループ)
def f2(x, y):
    # return pascal_triangle[x + y - 1][y - 1]
    n = x + y - 1
    r = y - 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# x 個の玉を y グループに分ける場合の数 (0個以上の玉のグループ)
def f(x, y):
    if x < y:
        return 0
    if x == 0 and y == 0:
        return 1
    if x == 0:
        return 0
    if y == 0:
        return 0
    return f2(x - y, y)


init()

# N = 5, K = 3
N, K = list(map(int, input().split()))

for i in range(1, K + 1):
    result = f(K, i) * (
        f(N - K, i - 1) +
        f(N - K, i) +
        f(N - K, i) +
        f(N - K, i + 1)
    )
    # print('0', i)
    # print('1', f(K, i))
    # print('2', f(N - K, i - 1))
    # print('3', f(N - K, i))
    # print('4', f(N - K, i + 1))
    print(result % 1000000007)
    # print("")

# for line in pascal_triangle:
#     print(line)
### BUGGY CODE ###

import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 2)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(min(dp[h:]))


### FIXED CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])
### BUGGY CODE ###

H, W = map(int, input().split())
A_arr = []
s_arr1 = []

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "#":
            s_arr1.append([i,j])


n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]
count = 0

while 1:
    if len(s_arr1) == H*W:
        break

    count += 1
    for i in range(len(s_arr1)):
        for n in range(4):
            tmp = [s_arr1[i][0] + n_list[n][0], s_arr1[i][1] + n_list[n][1]]
            if tmp[0] < 0 or tmp[0] >= H:
                pass
            elif tmp[1] < 0 or tmp[1] >= W:
                pass
            elif tmp in s_arr1:
                pass
            else:
                s_arr1.append(tmp)

    if len(s_arr1) == H*W:
        break

print(count)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A_arr = []
que = deque()
dist = [[-1 for i in range(W)] for i in range(H)]

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "#":
            que.append([i,j])
            dist[i][j] = 0

n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while 1:
    if len(que) == 0:
        break
    
    x, y = que.popleft()
    d = dist[x][y]
    for n in range(4):
        tmp = [x + n_list[n][0], y + n_list[n][1]]
        if tmp[0] < 0 or tmp[0] >= H:
            pass
        elif tmp[1] < 0 or tmp[1] >= W:
            pass
        elif dist[tmp[0]][tmp[1]] != -1:
            pass
        else:
            dist[tmp[0]][tmp[1]] = d + 1
            que.append([tmp[0], tmp[1]])


print(d)