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

import sys
from itertools import product
input = lambda:sys.stdin.buffer.readline().rstrip()

m, n, k = map(int, input().split())
item = {}
for _ in range(k):
    i, j, v = map(int, input().split())
    i -= 1; j -= 1
    item[i, j] = v

dp = [[0] * 4 for _ in range(n)]
for i in range(m):
    ndp = [[0] * 4 for _ in range(n)]
    for j, k in product(range(n), range(4)):
        # from top
        ndp[j][0] = max(ndp[j][0], dp[j][k])
        if (i, j) in item:
            ndp[j][1] = max(ndp[j][1], dp[j][k] + item[i, j])
        # from left
        if j > 0:
            ndp[j][k] = max(ndp[j][k], ndp[j - 1][k])
            if k > 0 and (i, j) in item:
                ndp[j][k] = max(ndp[j][k], ndp[j - 1][k - 1] + item[i, j])
    dp = ndp

print(max(dp[-1]))

### FIXED CODE ###

import sys
from itertools import product
input = lambda:sys.stdin.buffer.readline().rstrip()

m, n, k = map(int, input().split())
grid = [[0] * n for _ in range(m)]
for _ in range(k):
    i, j, v = map(int, input().split())
    i -= 1; j -= 1
    grid[i][j] = v

dp = [[0] * 4 for _ in range(n)]
for i in range(m):
    ndp = [[0] * 4 for _ in range(n)]
    for j, k in product(range(n), range(4)):
        # from top
        ndp[j][0] = max(ndp[j][0], dp[j][k])
        ndp[j][1] = max(ndp[j][1], dp[j][k] + grid[i][j])
        # from left
        if j > 0:
            ndp[j][k] = max(ndp[j][k], ndp[j - 1][k])
            if k > 0:
                ndp[j][k] = max(ndp[j][k], ndp[j - 1][k - 1] + grid[i][j])
    dp = ndp

print(max(dp[-1]))
### BUGGY CODE ###

from math import hypot,atan2,pi,cos
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

K = 400000
ans = 0
for i in range(K+1):
    t1 = 2*pi*i/K - pi
    r = 0
    for x,y in XY:
        t2 = atan2(y,x)
        a,b = (t1,t2) if t1<t2 else (t2,t1)
        if b-a > 3*pi/2:
            a += 2*pi
            a,b = b,a
        d = hypot(x,y) * cos(b-a)
        if d > 0:
            r += d
    ans = max(ans, r)
print(ans)

### FIXED CODE ###

from math import hypot,atan2
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
xy = sorted(XY, key=lambda x:atan2(x[1],x[0]))
xy += xy

ans = 0
for i in range(N):
    sx = sy = 0
    for j in range(N):
        x,y = xy[i+j]
        sx += x
        sy += y
        d = hypot(sx,sy)
        if d > ans:
            ans = d
print(ans)
### BUGGY CODE ###

import sys
from bisect import insort


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def debug_print(self):
        print(*('{:5d}'.format(i) for i in range(1, self.size + 1)))
        print(*('{:5d}'.format(self.sum(i)) for i in range(1, self.size + 1)))


Q = int(input())
queries = []
nums = []
for qi, line in enumerate(sys.stdin):
    q = list(map(int, line.split()))
    queries.append(q)
    if len(q) > 1:
        _, a, b = q
        nums.append((a, qi))
nums = sorted(nums)
min_a = nums[0][0]
n = len(nums)
num_d = {num: i for i, num in enumerate(nums)}

bit = Bit(n)
update_count = 0
update_list = []
sum_da = 0
sum_b = 0

for qi, q in enumerate(queries):
    if len(q) == 1:
        k = (update_count - 1) // 2
        x, qj = update_list[k]
        i = num_d[x, qj]
        d = x - min_a
        dn_cnt = (update_count + 1) // 2
        up_cnt = update_count - dn_cnt
        bsi = bit.sum(i + 1)
        up_sum = sum_da - bsi - d * up_cnt
        dn_sum = d * dn_cnt - bsi
        # print('k:{} x:{} i:{} d:{} up:{} dn:{}'.format(k, x, i, d, up_sum, dn_sum))
        res = up_sum + dn_sum + sum_b
        print(x, res)
    else:
        _, a, b = q
        sum_b += b
        update_count += 1
        insort(update_list, (a, qi))
        i = num_d[a, qi]
        d = a - min_a
        bit.add(i + 1, d)
        sum_da += d


### FIXED CODE ###

import sys
from heapq import heappush, heappushpop

Q = int(input())
high = []
low = []
sum_dh, sum_dl = 0, 0
sum_b = 0
MIN_X = -(10 ** 9)
buf = []

for qi, line in enumerate(sys.stdin):
    q = list(map(int, line.split()))
    if len(q) == 1:
        x = -low[0]
        dx = x - MIN_X
        ans_l = dx * len(low) - sum_dl
        ans_h = sum_dh - dx * len(high)
        buf.append('{} {}\n'.format(x, ans_l + ans_h + sum_b))
    else:
        _, a, b = q
        da = a - MIN_X
        sum_b += b
        if len(low) == len(high):
            h = heappushpop(high, a)
            heappush(low, -h)
            dh = h - MIN_X
            sum_dh += da - dh
            sum_dl += dh
        else:
            l = -heappushpop(low, -a)
            heappush(high, l)
            dl = l - MIN_X
            sum_dl += da - dl
            sum_dh += dl

print(''.join(buf))
### BUGGY CODE ###

# 最大公約数を求める関数
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return (a*b)/gcd(a,b)

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


m = lcm(a[0],a[1])
for i in range(1,len(a)):
    m = lcm(m,a[i])

res = int(sum([(m-1) % e for e in a]))
print(res)

### FIXED CODE ###

n = int(input())
res = sum(list(map(int, input().split()))) - n
print(res)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[]
[a.append(int(input())-1) for _ in range(q)]
i=[k]*n

for l in range(q):
    i = list(map(lambda x:x-1 ,i))
    i[a[l]] += 1

for l in range(n):
    if i[l] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[]
[a.append(int(input())-1) for _ in range(q)]
i=[k-q]*n

for l in range(q):
    i[a[l]] += 1

for l in range(n):
    if i[l] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N = int(input())
h=list(map(int,input().split()))
c = 0
a = h[0]
for i in range(0,N):
    s = 0
    if h[i] > a:
        a = h[i]
    else:
        for j in range(0,i):
            if h[j] >= h[i]:
                s += 1
        if s == i:
            c += 1
print(c)

### FIXED CODE ###

N = int(input())
h=list(map(int,input().split()))
c = 0
a = h[0]
for i in range(0,N):
    if a > h[i]:
        a = h[i]
    if a >= h[i]:
        c += 1
print(c)
### BUGGY CODE ###

import copy

N = int(input())
S = input()
list = [i for i in S]
anslist = []
for i in range(len(S)):
    s_i = list[i]
    for j in range(i+1,len(S)):
        s_j = list[j]
        for k in range(j+1,len(S)):
            s = s_i + s_j + S[k]
            anslist.append(s)


print(len(set(anslist)))


### FIXED CODE ###

_ = input()
S = input()
counter = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            idxi = S.find(str(i))
            if idxi ==-1:
                continue
            idxj = S.find(str(j),idxi+1)
            if idxj == -1:
                continue
            idxk = S.find(str(k),idxj+1)
            if idxk == -1:
                continue
            counter+=1
print(counter)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * (N+2)
cnt = 0

for i in range(N-1):
    if S[i]+S[i+1]=='AC':
        c[i+1]+=1

#print(c)

for i,j in zip(l,r):
    print(sum(c[:j])-sum(c[:i]))
 

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
    #c[i] = S[:i].count('AC')

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])
### BUGGY CODE ###

N, P = map(int, input().split())
S = list(map(int,list(input())))
U = []


for i in range(N+1):
    tmp = 0
    for j in range(i,N):
        tmp += S[j] * (10 ** (N-1-j))
    U.append(tmp % P)
    
def check1(i,j,P,S):
    return S[j] % P == 0

def check2(i,j,P,U):
    num = U[i]-U[j+1]
    return num == 0

def check(i,j,P,U,S):
    if P == 2 or P == 5:
        return check1(i,j,P,S)
    else:
        return check2(i,j,P,U)

ans = 0
for i in range(N):
    for j in range(i,N):
        if check(i,j,P,U,S):
            ans += 1

print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = list(map(int,list(input())))
U = [0 for i in range(N+1)]
POW = [1 for i in range(N)]

for i in range(N-1):
    POW[i+1] = (POW[i]*10) % P

for i in range(N):
    U[N-(i+1)] = (U[N-i] + S[N-1-i] * POW[i]) % P
    
def solve(U,S):
    if P == 2 or P == 5:
        return solve1(S)
    else:
        return solve2(U)
    
def solve1(S):
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    return ans

def solve2(U):
    ans = 0
    cnt = [0 for i in range(P)]
    for i in range(N+1):
        cnt[U[i]] += 1
    for i in range(P):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans

print(solve(U,S))
### BUGGY CODE ###

import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
from bisect import insort
sys.setrecursionlimit(10**9)

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

    ans = 0
    for mask in range(60): # 各桁ごとに、1を持つ数を探す
        one_sum = 0
        for a in A:
            one_sum += (a >> mask) & 1

        ans += one_sum * (N - one_sum) * 2**mask

    print(ans%(10**9+7))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

    ans = 0
    for mask in range(60): # 各桁ごとに、1を持つ数を探す
        one_sum = 0
        for a in A:
            one_sum += (a >> mask) & 1

        ans += one_sum * (N - one_sum) * 2**mask

    print(ans%(10**9+7))

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

n = int(input())
s = []
count = 0
for _ in range(n):
    s.append(sorted(input()))
for i in range(n-1):
    for j in range(i+1,n):
        if  s[i] == s[j] :
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
count = {}
ans = 0
for i in s:
    count[i] = count.get(i, 0) + 1
for key, value in count.items():
    ans += value * (value - 1) // 2
print(ans)
### BUGGY CODE ###

N = list(map(int, input().split()))[0]
A = list(map(int, input().split()))
def get_result(ary):
    d_old = -1
    for i in range(0, len(ary)):
        left = sum(ary[:i])
        right = sum(ary[i:])
        d = abs(left - right)
        if d > d_old and d_old > -1:
            return d_old
        else:
            d_old = d
    return d_old
print(get_result(A))

### FIXED CODE ###

import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(map(int, input().split())))
def get_result(ary):
    cumsum_left = np.cumsum(ary)
    cumsum_right = np.cumsum(ary[::-1])
    d = np.abs(cumsum_left[:-1] - cumsum_right[::-1][1:])
    return np.min(d)
print(get_result(A))
### BUGGY CODE ###

N = int(input())
S = str(input())
#i桁目までみて、1文字目がx、2文字目がy、3文字目がzのがあるか
dp = [[0]*10 for _ in range(N+1)]
dpp = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(N+1)]
dppp = [[[[0]*10 for _ in range(10)] for _ in range(10)] for _ in range(N+1)]

for i in range(N):
  now = int(S[i]) #i桁目 1index
  #dp[i+1][now] = 1
  for x in range(10):
    if x == now:
      dp[i+1][x] = 1
      #print(dp[i+1][x])
    else:
      dp[i+1][x] = max(dp[i][x],dp[i+1][x])
    for y in range(10):
      if y == now and dp[i][x] == 1:
        dpp[i+1][x][y] = 1
      else:
        dpp[i+1][x][y] = max(dpp[i][x][y],dpp[i+1][x][y])
      for z in range(10):
        if z == now and dpp[i][x][y] == 1:
          dppp[i+1][x][y][z] = 1
        else:
          dppp[i+1][x][y][z] = max(dppp[i][x][y][z],dppp[i+1][x][y][z])
#print(dp)
#print(dpp)
#print(dppp)
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      ans += dppp[N][i][j][k]
        
print(ans)       

### FIXED CODE ###

N = int(input())
Stemp = str(input())
S = []
for i in range(N):
  temp = int(Stemp[i])
  S.append(temp)
ans = set([])
L = [[] for _ in range(10)]
for i in range(N):
  L[S[i]].append(i)
#print(L)
for v in range(1000):
  a = v//100
  b = (v-a*100)//10
  c = v-a*100-b*10
  if not L[a]:
    continue
  left = min(L[a])
  Flag = False
  for x in L[b]:
    if x > left:
      mid = x
      Flag = True
      break
  if not Flag:
    continue
  Flag = False
  for y in L[c]:
    if y > mid:
      right = y
      Flag = True
      break
  if not Flag:
    continue
  ans.add(v)
  #print(v,left,mid,right)
print(len(ans))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))[::-1]

a1 = sorted(a[i] + b[j] for i in range(x) for j in range(y))[::-1]
a2 = sorted(a1[i] + c[j] for i in range(min(len(a1), k))
            for j in range(z))[::-1]
for i in range(k):
    print(a2[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))[::-1]

a1 = sorted(a[i] + b[j] for i in range(x) for j in range(y))[::-1]
a2 = sorted(a1[i] + c[j] for i in range(min(len(a1), k))
            for j in range(z))[::-1]
for i in range(k):
    print(a2[i])
### BUGGY CODE ###

from collections import defaultdict

N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 19

acc = defaultdict(int)

x = [-INF]
y = [-INF]

for ex, ey in xy:
	acc[(ex, ey)] = 1
	x.append(ex)
	y.append(ey)

x.sort()
y.sort()

for i in range(N):
	for j in range(N + 1):
		acc[(x[i+1], y[j])] += acc[(x[i], y[j])]

for j in range(N):
	for i in range(N + 1):
		acc[(x[i], y[j+1])] += acc[(x[i], y[j])]

ans = INF
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			for l in range(k + 1, N + 1):
				cnt = acc[(x[j], y[l])] - acc[(x[j], y[k-1])] - acc[(x[i-1], y[l])] + acc[(x[i-1], y[k-1])]
				if cnt >= K:
					sq = (x[j] - x[i]) * (y[l] - y[k])
					ans = min(ans, sq)

print(ans)


### FIXED CODE ###

from collections import defaultdict

N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 19

acc = defaultdict(int)

x = [-INF]
y = [-INF]

for ex, ey in xy:
	acc[(ex, ey)] = 1
	x.append(ex)
	y.append(ey)

x.sort()
y.sort()

for i in range(N):
	for j in range(N + 1):
		acc[(x[i+1], y[j])] += acc[(x[i], y[j])]

for j in range(N):
	for i in range(N + 1):
		acc[(x[i], y[j+1])] += acc[(x[i], y[j])]

ans = INF
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			for l in range(k + 1, N + 1):
				cnt = acc[(x[j], y[l])] - acc[(x[j], y[k-1])] - acc[(x[i-1], y[l])] + acc[(x[i-1], y[k-1])]
				if cnt >= K:
					sq = (x[j] - x[i]) * (y[l] - y[k])
					ans = min(ans, sq)

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

n, k = (map(int, input().split()))
h = list(map(int, input().split()))

dp = [0, abs(h[0] - h[1])]

for i in range(2, n):
    cost = []
    jump_range = min(i, k) + 1
    for n_jump in range(1, jump_range):
        jump_cost = dp[i - n_jump] + abs(h[i] - h[i - n_jump])
        cost.append(jump_cost)
    dp.append(min(cost))
    cost.clear()

print(dp[-1])


### FIXED CODE ###

n, k = (map(int, input().split()))
h = list(map(int, input().split()))

dp = [0, abs(h[0] - h[1])]

for i in range(2, n):
    cost = []
    jump_range = min(i, k) + 1
    for n_jump in range(1, jump_range):
        jump_cost = dp[i - n_jump] + abs(h[i] - h[i - n_jump])
        cost.append(jump_cost)
    dp.append(min(cost))
    cost.clear()

print(dp[-1])
### BUGGY CODE ###

n = int(input())

xy_sum = []
xy_dif = []
for i in range(n) :
    x, y = map(int, input().split())
    xy_sum.append(x + y)
    xy_dif.append(x - y)

max_dis = 0
for j in range(n) :
    for k in range(n - j) :
        dis = max(abs(xy_sum[j] - xy_sum[k]), abs(xy_dif[j] - xy_dif[k]))
        max_dis = max(max_dis, dis)
        
print(max_dis)

### FIXED CODE ###

n = int(input())

xy_sum = []
xy_dif = []
for i in range(n) :
    x, y = map(int, input().split())
    xy_sum.append(x + y)
    xy_dif.append(x - y)

print(max(abs(max(xy_sum) - min(xy_sum)), abs(max(xy_dif) - min(xy_dif))))
### BUGGY CODE ###

l,r = map(int,input().split())
ans = 2019

if l == 0:
    print(0)
    quit()

for i in range(l,r):
    for j in range(l+1,r+1):
        if ans == 0:
            break
        ans = min(ans,i*j%2019)

print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
ans = 2019

for i in range(l,min(r+1,l+2020)):
    for j in range(i+1,min(r+1,l+2020)):
        if ans == 0:
            break
        ans = min(ans,i*j%2019)

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

n,q=map(int,input().split())
S=input()
for i in range(q):
  l,r=map(int,input().split())
  s=S[l-1:r]
  cnt=s.count('AC')
  print(cnt)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*(n)
for i in range(n-1):
  if s[i]=='A' and s[i+1]=='C':
    a[i+1]=a[i]+1
  else:
    a[i+1]=a[i]
for i in range(q):
  l,r=map(int,input().split())
  ans=a[r-1]-a[l-1]
  print(ans)
### BUGGY CODE ###

n = int(input())
n = str(n)
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
ans = 0
for i in range(len(n_list) - 1):
    num = n_list[i]
    if (num <= 5 and n_list[i + 1] < 5) or num < 5:
        # pay += num * 10 ** k
        ans += num
    else:
        n_list[i + 1] += 1
        ans += 10 - n_list[i]
    k += 1

# pay += n_list[-1] * 10 ** k
ans += n_list[-1]
print(ans)
# oturi = pay - int(n)
# ans = 0
#
# for i in str(pay):
#     ans += int(i)
# for i in str(oturi):
#     ans += int(i)
# print(ans)


### FIXED CODE ###

n = input()
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
ans = 0
for i in range(len(n_list) - 1):
    num = n_list[i]
    if num < 5:
        ans += num
    elif (num <= 5 and n_list[i + 1] < 5):
        ans += num
    else:
        n_list[i + 1] += 1
        ans += 10 - num

ans += n_list[-1]
print(ans)
### BUGGY CODE ###

n, a, b = map(int, input().split())
r = 0
n2 = 0
if n < a:
	r = n
elif a == 0:
	r = 0
else:
	n2 = n
while n2 > 0:
	if (n2 - a < 1):
		r = r + n2
		n2 = 0
		break
	r = r + a
	n2 = n2 - a - b
print(r)

### FIXED CODE ###

n, a, b = map(int, input().split())
t = a + b
count = t if t > 0 else 0
r = 0
if count == 0:
	r = 0
else:
	d = int(n/t)
	if d*t == n:
		r = d * a
	else:
		r = d * a
		e = n - d*t
		if e <= a:
			r = r + e
		else:
			r = r + a
print(r)
### BUGGY CODE ###

from collections import defaultdict
        

obj = defaultdict(lambda: 1)

N=int(input())
ANA=[]
L=[]
for i in range(N):
    k=sorted([x for x in input()])
    if k in L:
        obj[L.index(k)]+=1
    else:
        L.append(k)

result=0
for i in obj.values():
    if i and i-1:
        result+=i*(i-1)/2
    
print(int(result))


### FIXED CODE ###

from collections import defaultdict
        

obj = defaultdict(lambda: 1)

N=int(input())
ANA=[]
L=set([])
for i in range(N):
    k="".join(sorted([x for x in input()]))
    if k in L:
        obj[k]+=1
    else:
        L.add(k)

result=0
for i in obj.values():
    if i and i-1:
        result+=i*(i-1)/2
    
print(int(result))
### BUGGY CODE ###

import math

n = int(input())
ans = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += math.gcd(i, math.gcd(j,k))

print(ans)

### FIXED CODE ###

import math

n = int(input())
ans = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += math.gcd(i, math.gcd(j,k))

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

s=input()
x,y=map(int,input().split())
ct=0
XY=[]
for i in range(len(s)):
  if s[i]=="F":
    ct+=1
  else:
    XY.append(ct)
    ct=0
XY.append(ct)
x-=XY[0]
X=XY[2::2]
Y=XY[1::2]


def chk(Z,z):
  tot,nz=sum(Z),len(Z)
  if tot==0:
    if z==0:
      return True
    else:
      return False
  elif abs(z)>tot:
    return False
  else:
    DP=[[False]*(2*tot+1) for _ in range(nz+1)]
    DP[0][tot]=True
    for i in range(nz):
      zz=Z[i]
      for j in range(2*tot+1):
        if j+zz<2*tot+1 and DP[i][j+zz]==True:
          DP[i+1][j]=True
        if j-zz>=0 and DP[i][j-zz]==True:
          DP[i+1][j]=True
    return DP[nz][z+tot]

if chk(X,x) and chk(Y,y):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s=input()
x,y=map(int,input().split())
ct=0
XY=[]
for i in range(len(s)):
  if s[i]=="F":
    ct+=1
  else:
    XY.append(ct)
    ct=0
XY.append(ct)
x-=XY[0]
X=XY[2::2]
Y=XY[1::2]


def chk(Z,z):
  tot,nz=sum(Z),len(Z)
  if tot==0:
    if z==0:
      return True
    else:
      return False
  elif abs(z)>tot:
    return False
  else:
    DP=[[False]*(2*tot+1) for _ in range(nz+1)]
    DP[0][tot]=True
    for i in range(nz):
      zz=Z[i]
      for j in range(2*tot+1):
        if j+zz<2*tot+1 and DP[i][j+zz]==True:
          DP[i+1][j]=True
        if j-zz>=0 and DP[i][j-zz]==True:
          DP[i+1][j]=True
    return DP[nz][z+tot]

if chk(X,x) and chk(Y,y):
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from collections import deque

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

d = [[-1] * w for _ in range(h)]


def bfs():
    q = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append((j, i))
                d[i][j] = 0

    dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

    ans = 0
    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy
            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 and a[vy][vx] == "." and d[vy][vx] == -1:
                d[vy][vx] = d[uy][ux] + 1
                ans = max(ans, d[vy][vx])
                q.append((vx, vy))

    return ans


ans = bfs()
print(ans)


### FIXED CODE ###

from scipy.ndimage import distance_transform_cdt


def main():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


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


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

nb=n//b

xmax=0
if n<b:
    xmax=a*n//b
else:
    xmax=0
    for xb in range(nb):
        xv=(a*xb*b+a*(b-1))//b-a*xb
        xmax=max(xmax,xv)
    xb=nb
    xv=(a*xb*b+a*n%b)//b-a*xb
    xmax=max(xmax,xv)

print(xmax)    



### FIXED CODE ###

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

nb=n//b

#xmax=0
if n<b:
    xmax=a*n//b
else:
    xmax=0
#    for xb in range(nb):
#        xv=(a*xb*b+a*(b-1))//b-a*xb
#        xmax=max(xmax,xv)
    xb=nb-1
    xv=(a*xb*b+a*(b-1))//b-a*xb
    xmax=max(xmax,xv)
    xb=nb
    xv=(a*xb*b+a*n%b)//b-a*xb
    xmax=max(xmax,xv)

print(xmax)
### BUGGY CODE ###

def main():
  N, W = list(map(int, input().split()))
  Data = []
  for i in range(N):
    Data.append(list(map(int, input().split())))
  
  DP = [0 for i in range(W+1)]
  
  for i in range(N):
    for j in range(W - Data[i][0], -1, -1):
      k = j + Data[i][0]
      DP[k] = max(DP[j] + Data[i][1], DP[k])
  
  print(DP[-1])
  
main()


### FIXED CODE ###

def main():
  N, W = list(map(int, input().split()))
  Data = []
  for i in range(N):
    Data.append(list(map(int, input().split())))
  
  DP = [0 for i in range(W+1)]
  
  for i in range(N):
    for j in range(W - Data[i][0], -1, -1):
      k = j + Data[i][0]
      DP[k] = max(DP[j] + Data[i][1], DP[k])
  
  print(DP[-1])
  
main()