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

def resolve():
    H,N=(int(i) for i in input().split())
    magics=[[int(i) for i in input().split()] for j in range(N)]
    mx=2**31
    dpt=[mx for i in range(H+1)]
    dpt[-1]=0
    for i in range(H,0,-1):
        
        current=dpt[i]
        if current> dpt[0]:
            continue
        for m in magics:
            dpt[max(0,i-m[0])]=min(dpt[max(0,i-m[0])],current+m[1])
    print(dpt[0])

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    H,N=(int(i) for i in input().split())
    magics=[[int(i) for i in input().split()] for j in range(N)]
    mx=2**31
    dpt=[mx for i in range(H+1)]
    dpt[-1]=0
    for i in range(H,0,-1):
        
        current=dpt[i]
        if current> dpt[0]:
            continue
        for m in magics:
            dpt[max(0,i-m[0])]=min(dpt[max(0,i-m[0])],current+m[1])
    print(dpt[0])

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

import numpy as np

N, K, Q = map(int, input().split()) 
score = np.array([K]*N)

def change_score(N ,A, score):
    score = score - np.array([1]*N)
    score[A-1] = score[A-1] + 1
    return score

for i in range(Q):
    A = int(input())
    score = change_score(N, A, score)
    #print(score)

for i in score:
    if i > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split()) 
score = np.array([0]*N)

def change_score(N ,A, score):
    #score = score - np.array([1]*N)
    score[A-1] = score[A-1] + 1
    return score

for i in range(Q):
    A = int(input())
    score = change_score(N, A, score)
    #print(score)
    f_score = score

for i in f_score:
    if i + K - Q > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"


################ DANGER ################
test = ""
#test = \

########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  


def maximized(a):
    """
    1 -2 3 -4 5
    全探索より速い 
    """
    """
    a = list(map(int, input2().split()))
    print(A_Frog1(a))
    """
    dp = [0] * (len(a) + 1)
    for i in range(len(a)):
        dp[i+1] = max(dp[i], dp[i] + a[i])
    return dp[-1]


def A_Frog1(a):
    """
    4
    10 30 40 20
    ans 30
    """
    """
    2
    10 10
    ans 0
    """
    """
    6
    30 10 60 10 60 50
    ans 40
    """
    """
    input2()
    a = list(map(int, input2().split()))
    print(A_Frog1(a))
    """
    n, h = len(a), a
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(1, n - 1):
        dp[i+1] = min(
                dp[i-1] + abs(h[i+1] - h[i-1]), 
                dp[i] + abs(h[i+1] - h[i]))
    return dp[-1]
    
    
def B_Frog2(K, a):
    """
    5 3
    10 30 40 50 20
    ans 30
    """
    """
    3 1
    10 20 10
    ans 20
    """
    """
    2 100
    10 10
    ans 0
    """
    """
    10 4
    40 10 20 70 80 10 20 70 80 60
    ans 40
    """
    """
    n, k = map(int, input2().split())
    a = list(map(int, input2().split()))
    print(B_Frog2(k, a))
    """
    n, h = len(a), a
    dp = [0] + [float('inf')] * (n-1)
    for j in range(1, n):
        for i in range(max(0, j - K), j):
            dp[j] = min(dp[j], dp[i] + abs(h[j] - h[i]))
    return dp[-1]
    

if __name__ == "__main__":
    ################## IO ##################
    n, k = map(int, input2().split())
    a = list(map(int, input2().split()))
    print(B_Frog2(k, a))
    
    
    
    

### FIXED CODE ###

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

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

################ DANGER ################
test = ""
#test = \
"""
5 3
10 30 40 50 20
ans 30
0 20 30 40 30
"""

"""
3 1
10 20 10
ans 20
"""

"""
2 100
10 10
ans 0
"""

"""
10 4
40 10 20 70 80 10 20 70 80 60
ans 40
0 30 20 30 40 30 20 30 40 40
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  

n, k = map(int, input2().split())
a = list(map(int, input2().split()))
k = min(n-1, k)

def main(n, k, a):
    aa = np.concatenate([a])
    dp = np.concatenate([np.abs(aa - aa[0])[:k+1], 
                                np.zeros(n-k-1, dtype="int")])
    for i in range(k+1, n):
        dp[i] = np.min(dp[i-k:i] + np.abs(aa[i-k:i] - aa[i]))
    
    return dp[-1]


if __name__ == "__main__":
    print(main(n, k, a))
### BUGGY CODE ###

def findSumOfDigits(n):
    sum = 0
    while (n > 0):
        sum += n % 10
        n //= 10
    return sum

n = int(input())
total = findSumOfDigits(n)
if total % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())

if n % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
l2 = list(set(l))
l2.sort(reverse=True)
a = 0
for i in range(len(l2)-1):
  if 2 <= l.count(l2[i]) <= 3:
    a = l2[i]
    for j in range(i+1, len(l2)):
      if 2 <= l.count(l2[j]):
        print(a * l2[j])
        sys.exit()
  elif l.count(l2[i]) >= 4:
    print(l2[i]**2)
    sys.exit()
print(0)

### FIXED CODE ###

import collections as c

n = int(input())
co = c.Counter(list(map(int, input().split())))
cm = sorted(co.items(), key=lambda x:x[0], reverse=True)
a = 0
b = 0
for v,m in cm:
  if m >= 4:
    if a == 0:
      a = b = v
    else:
      b = v
    break
  elif m >= 2 and a == 0:
    a = v
  elif m >= 2 and a != 0:
    b = v
    break
print(a*b)
### BUGGY CODE ###

from collections import*
import sys
sys.setrecursionlimit(10**8)

n=int(input())
d=defaultdict(list)

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    q.append(tuple(sorted([a,b])))
    
#print(d)
m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=deque(range(1,m+1))
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            ckamo=colar.pop()
            if c==ckamo:
                colar.appendleft(ckamo)
                ckamo=colar.pop()
            dcolars[tuple(sorted([point,i]))]=ckamo
            BFS(d,i,ckamo)
    return dcolars

ans=BFS(d,1,0)

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



### FIXED CODE ###

from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            c+=1
            if c==m+1:
                c=1
            dcolars[tuple(sorted([point,i]))]=c
            BFS(d,i,c)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])
### BUGGY CODE ###

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

num = [False] * (3001)
for i in range(N):
    num[L[i]] = True

L.sort(reverse=True)

ans = 0
for a in range(N):
    for b in range(a+1,N):
        l = L[a]-L[b]
        r = min(L[a]+L[b],L[b])
        ans += sum(num[l+1:r])
        # print(l,r,ans)
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
from bisect import bisect_left
for i in range(N):
    for j in range(i+1,N):
        t = bisect_left(L,L[i]+L[j])
        ans += max(0, t-(j+1))
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=((a[i]-b[i])*(combination(i, k-1, mod=10**9+7)))%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod=10**9+7
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):
    return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=((a[i]-b[i])*(comb(i,k-1)))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            b[max(0,i-v)]+=1
            if i+v+1<n:
                b[i+v+1]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

import sys
input = sys.stdin.readline

from heapq import heappop,heappush
import math

xs,ys,xt,yt = map(int,input().split())
n = int(input())

v = [[xs,ys,0]]
for _ in range(n):
    v.append(list(map(int,input().split())))
v.append([xt,yt,0])

def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[] for i in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i != j:
            d_ij = dd(v[i],v[j])
            edges[i].append((d_ij,j))
            edges[j].append((d_ij,i))

def dijkstra(s,n,edges):
    #edges[source] = [(cost_1,target_1),(cost_2,target_2),...]
    #import 'heap'
    d = [float('inf')] * n
    d[s] = 0
    q = [[d[s],s]]
    while q:
        dist_u, u = heappop(q)
        for c, v in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q,[d[v],v])
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+2):
    for j in range(i+1,n+2):
        edges[i][j] = dd(v[i],v[j])
        edges[j][i] = dd(v[i],v[j])

def dijkstra(s,n,edges):
    #edges[i][j] : the cost of i→j
    #import 'heap'
    d = [float('inf') for _ in range(n)]
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(2)]
A=list(map(int,S[0].split(" ")))
B=list(map(int,S[1].split(" ")))
mon_left=0
hero_left=0
counter=0
mon_killed=0

for i in range(N):
  if i==0:
    mon_sum=A[i]+A[i+1]
  else:
    mon_sum=(A[i]+A[i+1])-mon_killed
  hero = B[i]
    
  while hero>0 and mon_sum>0:
    counter+=1
    mon_sum -= 1
    hero -= 1
  if mon_sum > 0:
    mon_killed = 0
  elif mon_sum < 0:
    mon_killed = abs(mon_sum)

print(counter)

### FIXED CODE ###

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

for i in range(n):
  if a[i] >= b[i]:
    m += b[i]
  else:
    b[i] -= a[i]
    if a[i+1] < b[i]:
      m += a[i+1]+a[i]
      a[i+1]=0
    else:
      a[i+1] -= b[i]
      m += b[i] + a[i]
      
print(m)
### BUGGY CODE ###

s,_,*q=open(0)
a=['','']
p=1
for q in q:
  try:
    q,f,c=q.split()
    a[(f<'2')^p]+=c
  except:p^=1
print(a[p^1][::-1]+s[:-1][::p or-1]+a[p])

### FIXED CODE ###

from collections import*
s,_,*q=open(0)
d=deque(s[:-1])
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:d+=c,
    else:d.appendleft(c)
  except:p^=1
print(''.join(d)[::p or-1])
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
ls = np.empty(M)
rs = np.empty(M)


for i in range(M):
    l, r = map(int, input().split())
    ls[i] = l
    rs[i] = r

min_diff_arg = np.argmin(rs - ls)
candidate = np.arange(ls[min_diff_arg], rs[min_diff_arg]+1, 1)

valid_counter = 0
for c in candidate:
    if ((ls <= c) * (c <= rs)).all():
        valid_counter += 1

print(valid_counter)


### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
ls = np.empty(M)
rs = np.empty(M)


for i in range(M):
    l, r = map(int, input().split())
    ls[i] = l
    rs[i] = r

if 0 <= (np.min(rs) - np.max(ls)):
    print(int(np.min(rs) - np.max(ls) + 1))
else:
    print(0)
### BUGGY CODE ###

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
            break
        c[xx][yy] = a
        qq.append((a+1,xx,yy))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)


### FIXED CODE ###

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
          break
        if c[xx][yy] == '.' or (c[xx][yy] != '.' and c[xx][yy] > a):
          c[xx][yy] = a
          qq.append((a+1,xx,yy))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
LR = [[0 for _ in range(N)] for _ in range(N)]

for j in range(M):
  l,r = map(int,input().split())
  LR[l-1][r-1] += 1

for i in range(N):
  for j in range(1,N):
    LR[i][j] += LR[i][j-1]

for _ in range(Q):
  p,q = map(int,input().split())
  ans = 0
  for i in range(q-p+1):
    ans += LR[p+i-1][q-1]
  print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
LR = [[0 for _ in range(N)] for _ in range(N)]

for j in range(M):
  l,r = map(int,input().split())
  LR[l-1][r-1] += 1

for i in range(N):
  for j in range(1,N):
    LR[i][j] += LR[i][j-1]

for _ in range(Q):
  p,q = map(int,input().split())
  ans = 0
  for i in range(q-p+1):
    ans += LR[p+i-1][q-1]
  print(ans)
### BUGGY CODE ###

import numpy as np


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

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

nparr = np.array(a)

tmp = 0
data = 0

for i in range(m):

        tmp = np.argmax(a)

        data = np.floor(a[tmp]/2)

        a = np.delete(a, tmp)

        a = np.append(a, data)


print(int(np.sum(a)))

### FIXED CODE ###

import heapq
import math

n,m = list(map(int,input().split()))
a = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(a)

for i in range(m):
	tmp = heapq.heappop(a)
	tmp = (math.floor(-tmp/2)) * (-1)
	heapq.heappush(a, tmp)

print(sum(a) * -1)
### BUGGY CODE ###

def fun(x):
    ret = 1
    while x:
        ret *= x
        x -= 1
    return ret

def cmb(n,r):
    if n==r: return 1
    else: return fun(n) // (fun(r)*fun(n-r))




n = int(input())

ss = [sorted(input()) for i in range(n)]
ss.sort()

tmp = ss[0]
sss = [0]*n
j = 0
for i in range(n):
    if tmp == ss[i]: sss[j]+=1
    else:
        tmp = ss[i]
        j += 1
        sss[j]+=1

ans = 0
for i in sss:
    if i-1: ans += cmb(i,2)
print(ans)

### FIXED CODE ###

n = int(input())
d = {}

for i in range(n):
    s = "".join(sorted(input()))
    if s in d: d[s] += 1
    else: d[s] = 1
ans = 0
for i in d.values():
    ans += (i*i-i)//2
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc051/tasks/abc051_b

# n n,
K, S = input().split()

# initialize
ans = 0

# logic: 全探索: 基本形
for i in range(int(K)+1):
    for j in range(int(K)+1):
        for k in range(int(K)+1):
            xyz = i + j + k
            if xyz == int(S):
                ans += 1

print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
count=0
for a in range(k+1):
  for b in range(k+1):
    if 0<=s-a-b<=k:
      count+=1
print(count)
### BUGGY CODE ###

S = input()
n = 0
while True:
    if '01' in S:
        i = S.index('01')
        S = S[0 : i] + S[i + 2:]
    elif '10' in S:
        i = S.index('10')
        S = S[0 : i] + S[i + 2:]
    else:
        break
    n += 1

print(2 * n)




### FIXED CODE ###

S = input()
A = [int(c) for c in S]

l = len(S)
L = [[0 for j in range(l + 1)] for i in range(2)]
R = [[0 for j in range(l + 1)] for i in range(2)]

for i in range(l):
    L[0][i + 1] = L[0][i]
    L[1][i + 1] = L[1][i]
    L[A[i]][i + 1] += 1

for i in range(l - 1, -1, -1):
    R[0][i] = R[0][i + 1]
    R[1][i] = R[1][i + 1]
    R[A[i]][i] += 1

k = 0
for a, b, c, d in zip(L[0], R[1], L[1], R[0]):
    k = max(k, min(a, b) + min(c, d))

print(k * 2)
### BUGGY CODE ###

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

ans = 0

for i in range(N-1) :
    if S[i] == "#" and S[i+1] == "." :
        S = S[:i+1] + "#" + S[i+2:]
        ans += 1
print(ans)



### FIXED CODE ###

N = int(input())
S = input()
ans = cnt = S.count(".")
for s in S :
    if s == "#" :
        cnt += 1
    else :
        cnt -= 1
    ans = min(ans,cnt)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
for _ in range(K+2):
    H.append(10**9)
dp = [10**9] * (N+K+1)
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i] + abs(H[i]-H[i+j]), dp[i+j])
print(dp[N-1])



### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
for _ in range(K+2):
    H.append(10**9)
dp = [10**9] * (N+K+1)
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i] + abs(H[i]-H[i+j]), dp[i+j])
print(dp[N-1])
### BUGGY CODE ###

s = input()
t = input()
ls, lt = len(s), len(t)
dp = [[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = ls, lt
ans = []
while(i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print(str(''.join(ans)))


### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
#back trace
ans = []
while i >= 0 and j >= 0:
    if dp[i+1][j+1] == dp[i][j] + 1 and s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else: i -= 1
ans.reverse()
print(''.join(ans))
### BUGGY CODE ###

n,x = map(int,input().split())
a = [int(x) for x in input().split()]
c =0
for i in range(n-1):
    if a[i]+a[i+1] <= x:
        continue
    else:
        while(a[i+1] != 0 and x!= a[i]+a[i+1]):
            a[i+1] = a[i+1]-1
            c += 1
    if a[i]+a[i+1] > x:
        while (a[i] != 0 and x != a[i] + a[i + 1]):
            a[i] = a[i] - 1
            c += 1
print(c)

### FIXED CODE ###

n,x = map(int,raw_input().split())
arr = map(int,raw_input().split())
su = arr[0]
ans = 0
for i in range(1,n):
    su += arr[i]
    if su > x:
        diff = min(arr[i],su-x)
        arr[i] -= diff
        su = arr[i-1]+arr[i]
        if su > x:
            diff1 = min(arr[i-1],su-x)
            arr[i-1] -= diff1
            su = arr[i-1]+arr[i]
            ans += diff1
        ans += diff
    su = arr[i]
print ans
### BUGGY CODE ###

from collections import deque
import copy
def bfs():
  H, W = map(int, input().split())
  maze = [list(input()) for i in range(H)]
  S = []
  for i in range(H):
    for j in range(W):
      if maze[i][j] == ".":
        maze[i][j] = float("inf")
        S.append([i, j])
      else:
        maze[i][j] = -1
  ans = 0
  for k in range(len(S)):
    maze1 = copy.deepcopy(maze)
    maze1[S[k][0]][S[k][1]] = 0
    q = deque([[S[k][0],S[k][1]]])
    while q:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty, nextx = y+i, x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs()

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()