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

import sys
readline = sys.stdin.buffer.readline

from collections import deque

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i])
            d[j][i] = 0
        else:
            pass

def bfs(d):
    m = 0
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                m = max(m,d[ny][nx])
                q.append([ny,nx])
    return d,m

d,m = bfs(d)
print(m)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
field = [ list(input()) for _ in range(h) ]

visited = [ [0]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i,0])
            visited[j][i] = 1
        else:
            pass

m = 0
while q:
    y,x,d = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif visited[ny][nx]==0:
            visited[ny][nx] = 1
            q.append([ny,nx,d+1])
            m = max(m,d+1)   
print(m)
### BUGGY CODE ###

h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]
s=[[0 for i in range(w)] for j in range(h)]
for i in range(m):
    x,y=map(int,input().split())
    s[x-1][y-1]=1
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
for i in range(h):
    if g[i]==max(g):
        G.append(i+1)
for i in range(w):
    if r[i]==max(r):
        R.append(i+1)
f=1
for i in range(len(G)):
    for j in range(len(R)):
        if s[G[i]-1][R[j]-1]==0:
            f=0
            break
print(max(g)+max(r) if f==0 else max(g)+max(r)-1)


### FIXED CODE ###

h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
d=max(g)
e=max(r)
for i in range(h):
    if g[i]==d:
        G.append(i+1)
for i in range(w):
    if r[i]==e:
        R.append(i+1)
f=0
for i in range(m):
    q=0
    p=0
    x=a[i][0]
    y=a[i][1]
    k=len(G)-1
    l=0
    j=(k+l)//2
    while k-l>1:
        j=(k+l)//2
        if G[j]>=x:
            k=j
        else:
            l=j
    if G[l]==x or G[k]==x:
        p=1

    k = len(R) - 1
    l = 0
    j = (k + l) // 2
    while k - l > 1:
        j = (k + l) // 2
        if R[j] >=y:
            k = j
        else:
            l = j
    if R[l] == y or R[k] == y:
        q = 1

    if p==q==1:
        f+=1
v=1
if f!=len(G)*len(R):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)
### BUGGY CODE ###

import collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            next = collections.deque()
            dist = []
            checked = []
            curmax = 0
            for k in range(h):
                a = [0]*w
                b = [0]*w
                dist.append(a)
                checked.append(b)
            next.append([i,j])
            while len(next) != 0:
                cur = next.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    t = cur[0]+dy_dx[l][0]
                    u = cur[1]+dy_dx[l][1]
                    if (0 <= t <= h-1) and (0 <= u <= w-1):
                        if checked[t][u] == 0:
                            if maze[t][u] == '.':
                                dist[t][u] = dist[cur[0]][cur[1]]+1
                                next.append([t,u])
                                curmax = max(curmax,dist[t][u])
            ans = max(ans,curmax)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)
### BUGGY CODE ###

s = input("")
q = int(input())
cnt = 1
for _ in range(q):
    list_q = list(map(str, input().split()))
    if list_q[0] == "1":
        cnt *= -1
    elif list_q[0] == "2":

        if list_q[1] == "1" and cnt == 1:
            s = list_q[2] + s
        elif list_q[1] == "1" and cnt == -1:
            s = s + list_q[2]
        elif list_q[1] == "2" and cnt == 1:
            s = s + list_q[2]
        elif list_q[1] == "2" and cnt == -1:
            s = list_q[2] + s

if cnt == 1:
    print(s)
elif cnt == -1:
    print(s[::-1])

### FIXED CODE ###

from collections import deque

ans = deque()
center_ans_1 = input()
center_ans = list(center_ans_1)
for i in range(len(center_ans)):
    a = center_ans[i]
    ans.append(a)

q = int(input())
list_data = [ list(map(str,input().split(" "))) for i in range(q)]
#print(list_data)
re = 0
for i in range(q):
    list_a = list_data[i]
    #print(list_a)
    if list_a[0] == "1":
        re += 1
    elif list_a[0] == "2":
        if list_a[1] == "1":
            if re % 2 == 0:
                ans.appendleft(list_a[2])
            elif re % 2 == 1:
                ans.append(list_a[2])
        elif list_a[1] == "2":
            if re % 2 == 0:
                ans.append(list_a[2])
            elif re % 2 == 1:
                ans.appendleft(list_a[2])

if re % 2 == 1:
    ans.reverse()

print("".join(ans))
### BUGGY CODE ###

n, q = map(int, input().split())

A = [0 for i in range(n + 1)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        A[x] += y
    else:
        s = sum(A[x:y+1])
        print(s)

### FIXED CODE ###

import sys
import math

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

# make a balanced binary tree.
n = 2 ** math.ceil(math.log(n, 2))

A = [0 for i in range(2 * n - 1)]

# operating function
def add(i, x):
    # note; argument i is 1-based.
    i += n - 2
    A[i] += x

    while i > 0:
        i = (i - 1) // 2
        A[i] += x

def getSum(s, t, k, l, r):
    if r < s or t < l:
        return 0
    elif s <= l and r <= t:
        return A[k]
    else:
        mid = (l + r) // 2
        lsum = getSum(s, t, k * 2 + 1, l, mid)
        rsum = getSum(s, t, k * 2 + 2, mid + 1, r)
        return lsum + rsum

for s_i in f_i:
    com, x, y = map(int, s_i.split())
    if com == 0:
        add(x, y)
    else:
        ans = getSum(x, y, 0, 1, n)
        print(ans)
### BUGGY CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0, 0, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.append((nx, ny, c+1, d, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                q.append((nx, ny, c+1, d, e+1))

print(-1 if ans == float("inf") else ans)

### FIXED CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e+1))

print(-1 if ans == float("inf") else ans)
### BUGGY CODE ###

from math import gcd

K = int(input())
ans = 0

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

### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0

for i in range(1, K + 1):
  for j in range(1, K + 1):
    for k in range(1, K + 1):
      ans += gcd(gcd(i, j), k)
      
print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    while True:
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p < M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    for i in range(N):
        for j in range(s):
            if A[i] + A[j] >= m:
                r += A[i] + A[j]
            if A[i] + A[j] < m:
                s = j + 1
                break
    return r - (t - M) * m
    
print(main())
    


### FIXED CODE ###

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())
### BUGGY CODE ###

import math

def calc(a, b, c):
    return a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a

N = int(input())

for i in range(1, N+1):
    ans = 0
    for x in range(1, round(math.sqrt(i))):
        if x**2 > i:
            break
        t1 = i-x**2
        for y in range(1, t1):
            if y**2 > t1:
                break
            t2 = t1-y**2
            for z in range(1, t2):
                if z**2 > t2:
                    break
                tmp = calc(x, y, z)
                if tmp > i:
                    break
                if tmp == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())

ans = [0 for _ in range(10**4+50)]

for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if tmp < 10**4+50:
                ans[tmp] += 1

for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

A, B = map(int, input().split())
tmp = max(A, B)
flag = True
for i in range(tmp):
    if abs(i - A) == abs(i - B):
        print(i)
        flag = False

if flag == True:
    print("IMPOSSIBLE")

### FIXED CODE ###

A, B = map(int, input().split())
K = int((A + B) / 2)
if abs(K - A) == abs(K - B):
    print(K)
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n, m = map(int, input().split())
fri_dic = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in fri_dic:
    fri_dic[a] = set()
  if b not in fri_dic[a]:
    fri_dic[a].add(b)
  if b not in fri_dic:
    fri_dic[b] = set()
  if a not in fri_dic[b]:
    fri_dic[b].add(a)
visited = set()
max_count = 0
for i in range(1, n + 1):
  #print(visited)
  if i in visited:
    continue
  queue = [i]
  con_visited = set()
  while queue:
    p = queue.pop(0)
    if p in visited:
      continue
    visited.add(p)
    con_visited.add(p)
    if p not in fri_dic:
      continue
    for j in fri_dic[p]:
      queue.append(j)
  if len(con_visited) > max_count:
    max_count = len(con_visited)
print(max_count)


### FIXED CODE ###

n, m = map(int, input().split())
fri_dic = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in fri_dic:
    fri_dic[a] = set()
  if b not in fri_dic[a]:
    fri_dic[a].add(b)
  if b not in fri_dic:
    fri_dic[b] = set()
  if a not in fri_dic[b]:
    fri_dic[b].add(a)
visited = set()
max_count = 0
for i in range(1, n + 1):
  #print(visited)
  if i in visited:
    continue
  stack = [i]
  con_visited = set()
  while stack:
    p = stack.pop()
    if p in visited:
      continue
    visited.add(p)
    con_visited.add(p)
    if p not in fri_dic:
      continue
    for j in fri_dic[p]:
      stack.append(j)
  if len(con_visited) > max_count:
    max_count = len(con_visited)
print(max_count)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(N - 1, -1, -1):
            if S[i] != S[j]:
                dpi[j] = 0
            else:
                dpi[j] = dpi1[j + 1] + 1
    result = 0
    for i in range(N):
        dpi = dp[i]
        for j in range(i + 1, N):
            t1 = dpi[j]
            t2 = j - i
            if t1 > t2:
                t1 = t2
            if t1 > result:
                result = t1
    print(result)


main()


### FIXED CODE ###

N = int(input())
S = input()

result = 0
for i in range(N - 1, 0, -1):
    if i <= result:
        break
    t = 0
    for j in range(N - i):
        if S[j] == S[j+i]:
            t += 1
            if t > result:
                result = t
            if result == i:
                break
        else:
            t = 0

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

n,m=map(int,input().split())
a=[[]*i for i in range(n)]
tmp=[]
for i in range(m):
    p,y=map(int,input().split())
    p-=1
    a[p].append([y,i])
for k in range(n):
    if len(a[k])>0:
        a[k].sort()
        for j in a[k]:
            u=str(k+1).zfill(6)
            d=str(a[k].index(j)+1).zfill(6)
            ans=u+d
            tmp.append([ans,j[1]])
tmp.sort(key=lambda x:x[1])
for b in tmp:
    print(b[0])

### FIXED CODE ###

n, m = map(int, input().split())
cnt = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = map(int, input().split())
    cnt[p].append((y, i))
buf = [None] * m
for p, l in enumerate(cnt):
    if not l:
        continue
    l.sort()
    for j, (y, i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p, j + 1)
print('\n'.join(buf))
### BUGGY CODE ###

q = int(input())


def isPrime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = int(n**0.5)+1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
    return True


ans = []
for _ in range(q):
    l, r = map(int, input().split())
    cnt = 0
    for i in range(l, r+1, 2):
        if isPrime(i) and isPrime((i+1)//2):
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print(ans[i])

### FIXED CODE ###

n_max = 10 ** 5 + 10
sieve = [0, 0] + [1]*n_max
m = 2
while m * m <= n_max:
    if sieve[m]:
        for n in range(2*m, n_max, m):
            sieve[n] = 0
    m += 1

ok = [0]*n_max
cums = [0]
for n in range(n_max):
    if sieve[n] and sieve[(n+1)//2]:
        ok[n] = 1
    cums.append(cums[-1]+ok[n])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cums[r+1]-cums[l])
### BUGGY CODE ###

def mx(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[-i-1]
	return sum
	
def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		if mx(ls,m) < s: return 0
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
### BUGGY CODE ###

S=input()
N=len(S)


T=[]
T.append(0)
tmp=""
for i in range(N):
    s=S[N-1-i]
    tmp=s+tmp
    T.append(int(tmp))

x=dict()
for i in range(len(T)):
    val=T[i]%2019
    x[val]=0 
for i in range(len(T)):
    val=T[i]%2019
    x[val]+=1
ans=0
for idx in x:
    val=x[idx]
    ans+=((val*(val-1))//2)

print(ans)

### FIXED CODE ###

S=input()
N=len(S)
#「連続する区間」についての問題では、”累積和的なもの”をとるのが定石である。
#Sの連続する区間が、右からa文字分から、右からb文字分を取り除いたものであるとき
#その区間の整数が2019の倍数になるということは、s[a]とs[b]を2019で割ったあまりが等しい
#十分条件であることは分かったが、必要条件であるのか
#結論として必要条件でもある
#なぜなら2019と10は互いに素であるからである。

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019 
    d[r]+=1

ans=0

print(sum(i*(i-1)//2 for i in d))
### BUGGY CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n, x, m = map(int, input().split())
    d2 = [d[i] % m for i in range(k)]
    a = (n - 1) // k
    b = (n - 1) % k
    e = d2[:b]
    c = (x + sum(d2) * a + sum(e)) // m - (x // m)
    print(n - 1 - c - d2.count(0) * a - e.count(0))

### FIXED CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n, x, m = map(int, input().split())
    d2 = [d[i] % m for i in range(k)]
    sum_d = [0] * (k + 1)
    count_d = [0] * (k + 1)
    for i in range(k):
        sum_d[i + 1] = sum_d[i] + d2[i]
        if d2[i] == 0:
            count_d[i + 1] = count_d[i] + 1
        else:
            count_d[i + 1] = count_d[i]
    a = (n - 1) // k
    b = (n - 1) % k
    c = (x + sum_d[k] * a + sum_d[b]) // m - (x // m)
    print(n - 1 - c - count_d[k] * a - count_d[b])
### BUGGY CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = [INF] * (W + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(A, W+1):
        dp[j] = min(dp[j], dp[j-A] + B)
print(min(dp[H:]))

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
for i in range(M):
    P[i], Y[i] = map(int, input().split())

p_min = min(P)
p_max = max(P)

ANS = [0] * M
for pivot in range(p_min, p_max + 1):
    if pivot not in P:
        continue
    indices = [i for i, p in enumerate(P) if p == pivot]
    extracted_y = [Y[i] for i in indices]
    extracted_y.sort()
    for i in indices:
        ANS[i] = extracted_y.index(Y[i])

for p, y in zip(P, ANS):
    print('{:06}{:06}'.format(p, y + 1))


### FIXED CODE ###

N, M = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(M)]
P = {c[0]: [] for c in C}
for c in C:
    P[c[0]].append(c[1])
for p in P:
    P[p].sort()
    P[p] = {P[p][i]: i + 1 for i in range(len(P[p]))}
for c in C:
    print('{:06}{:06}'.format(c[0], P[c[0]][c[1]]))
### BUGGY CODE ###

n, m = map(int, input().split())
ans = 0
for i in range(1, m//n+1):
    if not m%i:
        ans = i
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
if is_prime(m):
    print(1)
else:
    for i in range(m//n, 0, -1):
        if not m%i:
            print(i)
            break
### BUGGY CODE ###

from collections import deque
s = deque(input())
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += int(s.pop())*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)