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

from heapq import *
def main():
    import numpy as np
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    inf=float('inf')
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        xy1=np.array([x1,y1])
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            xy2=np.array([x2,y2])
            d_temp=max(0,np.linalg.norm(xy1-xy2)-r1-r2)
            g[i].append([j,d_temp])
            g[j].append([i,d_temp])
    d=[10**10]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append([j,i])
    heapify(h)
    while h:
        i,j=heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heappush(h,[l+i,k])
    print(d[1])
main()

### FIXED CODE ###

def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append((j,d_temp))
            g[j].append((i,d_temp))
    d=[0]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append((j,i))
    heapq.heapify(h)
    while h:
        i,j=heapq.heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heapq.heappush(h,(l+i,k))
    print(d[1])
main()
### BUGGY CODE ###

N,price  = map(int,input().split())
answer = []
for i in range(N+1):
    if price<10000*i and len(answer) != 0 :
        break
    else:
        for j in range(N-i+1):
            if price<10000*i+5000*j and len(answer) != 0:
                break
            else:
               for k in range(N-i-j+1):
                    if price<10000*i+5000*j+1000*k and len(answer) != 0:
                        break
                    if N==i+j+k and price == 10000*i+5000*j+1000*k:
                        answer = [i,j,k]
if(len(answer)!=0):
    for i in range(3):
        print(answer[i], end = " ")
else:
    for i in range(3):
        print(-1, end = " ")

### FIXED CODE ###

N,Y=map(int,input().split())
for x in range(N+1):
    for y in range(N-x+1):
        z=N-x-y
        if 0<=z<=2000 and 10000*x+5000*y+1000*z==Y:
            print(x,y,z)
            exit()
print(-1,-1,-1)
### BUGGY CODE ###

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

r = len(S.replace("G", "").replace("B", ""))
g = len(S.replace("R", "").replace("B", ""))
b = N - r - g

ans = r * g
ans = ans * b

for i in range( N ):
    for j in range(i, N):
        k = 2 * j - i
        if (i < j) & (j < k) & (k < N) :
            s = S[i] + S[j] + S[k]
            if ("R" in s) & ("G" in s) & ("B" in s):
                ans -= 1

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
r = len(S.replace("G", "").replace("B", ""))
g = len(S.replace("R", "").replace("B", ""))
b = N - r - g

ans = r * g
ans = ans * b

for i in range( N ):
    for j in range(i, int((N+i)/2 + 1)):
        k = 2 * j - i
        if k < N:
            s = S[i] + S[j] + S[k]
            if ("R" in s) & ("G" in s) & ("B" in s):
                ans -= 1

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

n, t = map(int, input().split())
a = list(map(lambda x: int(x), input().split()))
#a = list(map(lambda x: int(x), in1.split()))
w_a = []
str_a = 0

for idx1 in range(len(a) - 1):
    w_a.append(a[idx1])
    if a[idx1 + 1] - min(w_a) > str_a:
        RC = 1
        str_a = a[idx1 + 1] - min(w_a)
    elif a[idx1 + 1] - min(w_a) == str_a:
        RC += 1

print(RC)


### FIXED CODE ###

n, t = map(int, input().split())
a = list(map(lambda x: int(x), input().split()))
#a = list(map(lambda x: int(x), in1.split()))
b = []
strlow = a[0]

for idx1 in range(1, len(a)):
    b.append(a[idx1] - strlow)
    if a[idx1] < strlow:
        strlow = a[idx1]

print(b.count(max(b)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            elif a[c[1]][0] > c[2]:
                a[c[1]].appendleft(c[2])
            else:
                left = 0
                right = len(a[c[1]])-1
                while right - left > 1:
                    mid = (right - left)//2
                    if a[c[1]][mid] < c[2]:
                        left = mid
                    else:
                        right = mid
                a[c[1]].insert(right, c[2])
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()




### FIXED CODE ###

import heapq

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        heapq.heappush(a[c[1]],-c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(-a[c[1]][0])
    else:
        if a[c[1]]:
            heapq.heappop(a[c[1]])
### BUGGY CODE ###

import itertools
N=int(input())
S=input()

ans=0

for i in itertools.product(range(0,10),repeat=3):

    isOK=[False]*3
    
    for x in range(len(S)):
        if isOK[0] and isOK[1]:
            if int(S[x])==i[2]:
                ans+=1
                break
        elif isOK[0]:
            if int(S[x])==i[1]:
                isOK[1]=True
        else:
            if int(S[x])==i[0]:
                isOK[0]=True

print(ans)

### FIXED CODE ###

import itertools
N=int(input())
S=input()

ans=0

for i in itertools.product(range(0,10),repeat=3):

    isOK=[False]*3
    
    for x in range(len(S)):
        if isOK[0] and isOK[1]:
            if int(S[x])==i[2]:
                ans+=1
                break
        elif isOK[0]:
            if int(S[x])==i[1]:
                isOK[1]=True
        else:
            if int(S[x])==i[0]:
                isOK[0]=True

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

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2 - n):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

import numpy as np

def main():
    h, n = map(int, input().split())
    ab = []
    for i in range(n):
        ab.append(tuple(map(int, input().split())))

    dp = np.zeros(h+1, dtype='i8')
    for i in range(h):
        dp[i] = 10**18
    for i in range(h, 0, -1):
        for j in range(n):
            dp[max(0, i-ab[j][0])] = min(dp[max(0, i - ab[j][0])], dp[i] + ab[j][1])

    print(dp[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = []
    for i in range(n):
        ab.append(tuple(map(int, input().split())))

    dp = []
    for i in range(h+1):
        dp.append(10**18)
    dp[h] = 0
    for i in range(h, 0, -1):
        for j in range(n):
            dp[max(0, i-ab[j][0])] = min(dp[max(0, i - ab[j][0])], dp[i] + ab[j][1])

    print(dp[0])


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

def lam(x):
	ans=1
	for i in range(1,x+1):
		ans*=i
	return ans
n,m=map(int,input().split())
n,m=min(n,m),max(n,m)
mod=10**9+7
if n<m-1:
	print(0)
	exit()
if n+1==m:
	print(lam(n)*lam(m)%mod)
else:
	print(2*lam(n)**2%mod)


### FIXED CODE ###

def lam(x,mo):
	ans=1
	for i in range(1,x+1):
		ans*=i
		ans%=mo
	return ans
n,m=map(int,input().split())
n,m=min(n,m),max(n,m)
mod=10**9+7
if n<m-1:
	print(0)
	exit()
if n+1==m:
	print(lam(n,mod)*lam(m,mod)%mod)
else:
	print(2*(lam(n,mod)**2)%mod)
### BUGGY CODE ###

from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=0
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if taisenzumi[i]:continue
		if data[i]:
			aite=data[i][0]
			# print(data[i],aite)
			if taisenzumi[aite-1]:continue
			# print(data[i],aite)
			if data[aite-1][0]==i+1:
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=1
			else:continue
	if not flag:
		break
else:
	print(count)
	exit()
print(-1)




### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    M=[None]*n
    for i in range(n):
        M[i]=list(map(lambda x:int(x)-1,input().split()))[::-1]

    # i が誰かしらと対戦できるか
    def check(i):
        if(not M[i]): # 既に試合を終えている
            return False
        j=M[i][-1]
        if(not M[j]): # これは起こり得ない
            return False
        return i==M[j][-1]

    # 初日に対戦できる人をピックアップ
    # 重複が起こるが、後で unique を取る
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i # i<j
            Q.append((i,j))

    # 処理を行なっていく
    day=0
    nQ=[] # 次の試合相手
    while(Q):
        # Q には重複があるので unique
        Q=list(set(Q))
        # 先に全ての試合を終わらせる必要がある
        for i,j in Q:
            M[i].pop(); M[j].pop()
        # 試合を終えた人は次の試合を行える可能性がある
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print(day if(all(M[i]==[] for i in range(n))) else "-1")
resolve()
### BUGGY CODE ###

size, jumps = map(int, input().split())
array = list(map(int, input().split()))
dp = [9999999999] * size
dp[0]= 0
for i in range(size):
  for j in range(i + 1, i+jumps+1):
    if j < size:
      dp[j] = min(dp[j], dp[i]+abs(array[i] - array[j]))
print(dp[size-1])

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

xs, ys, xt, yt = map(int, input().split())
n = int(input())
X = [[0, 0, 0] for _ in range(n+2)]
X[0] = [xs, ys, 0]
X[n+1] = [xt, yt, 0]
R = [0]*n
for i in range(n):
    x, y, r = map(int, input().split())
    X[i+1] = [x, y, r]

import math
edge = [[] for _ in range(n+2)]
for i in range(n+1):
    x1, y1, r1 = X[i]
    for j in range(i+1, n+2):
        x2, y2, r2 = X[j]
        l = math.sqrt((x1-x2)**2+(y1-y2)**2)
        edge[i].append((max(l-r1-r2, 0), j))
        edge[j].append((max(l-r1-r2, 0), i))

import heapq
def dijkstra_heap(s):
    d = [float("inf")] * (n+2)
    used = [True] * (n+2) #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(0)
print(d[-1])

### FIXED CODE ###

xs, ys, xt, yt = map(int, input().split())
n = int(input())
X = [[0, 0, 0] for _ in range(n+2)]
X[0] = [xs, ys, 0]
X[n+1] = [xt, yt, 0]
R = [0]*n
for i in range(n):
    x, y, r = map(int, input().split())
    X[i+1] = [x, y, r]

import math
edge = [[] for _ in range(n+2)]
for i in range(n+1):
    x1, y1, r1 = X[i]
    for j in range(i+1, n+2):
        x2, y2, r2 = X[j]
        l = math.sqrt((x1-x2)**2+(y1-y2)**2)
        edge[i].append((max(l-r1-r2, 0), j))
        edge[j].append((max(l-r1-r2, 0), i))

import heapq
def dijkstra_heap(s):
    d = [float("inf")] * (n+2)
    used = [True] * (n+2) #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(0)
print(d[-1])
### BUGGY CODE ###

n = int(input())

ans = 1

for i in range(n):
	
	ans = ans * (i+1)

print(ans%1000000007)



### FIXED CODE ###

n = int(input())

#nの階乗の計算 n!
import math
k = math.factorial(n)

print(k%1000000007)
### BUGGY CODE ###

S = [int(i) for i in input()]
from collections import Counter
def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*10**i)%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))

### FIXED CODE ###

S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
ans = 1

for i in range(1, n+1):
  ans *= i
  ans %= 10**9+7

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

N,K = map(int,input().split())
ps = list(map(int,input().split()))

dices =[]
dicesSum=[]
for i in range(N-K+1):
    l= ps[i:i+K]
    dices.append(l)
    dicesSum.append(sum(l))


max_value = max(dicesSum)
max_index = dicesSum.index(max_value)

exp=0
for p in dices[max_index]:
    exp += 0.5*p +0.5
print(exp)


### FIXED CODE ###

N,K = map(int,input().split())
ps = list(map(int,input().split()))

dicesSum=[]
l1=ps[0:K]
dicesSum.append(sum(l1))

if K==N:
    exp= (K+ dicesSum[0])/2
    print(exp)
else:
    for i in range(1,N-K+1):
        dicesSum.append(dicesSum[i-1]-ps[i-1]+ps[i+K-1])
    max_value = max(dicesSum)
    exp= (K+ max_value)/2
    print(exp)
### BUGGY CODE ###

K = int(input())

GCD_table = [[-1] * (K + 1) for i in [1] * (K + 1)]
#print(GCD_table)

def GCD(a: int, b: int) -> int:
    if a <= b:
        return GCD_Recursive(b, a)
    else:
        return GCD_Recursive(a, b)

def GCD_Recursive(a: int, b: int) -> int:
    if GCD_table[a][b] != -1:
        return GCD_table[a][b]

    remain = a % b
    if remain == 0:
        # print("before:", GCD_table)
        # print("a", a)
        # print("b", b)
        GCD_table[a][b] = b
        # print("rewrite!")
        # print("after:", GCD_table)
        return b
    else:
        return GCD_Recursive(b, remain)
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(i, GCD(j, k))

# print(GCD_table)
print(ans)


### FIXED CODE ###

def main():
  import math
  N = int(input())
  gcd={}
  ans=0
  for i in range(1,N+1):
    for j in range(1, N+1):
      key=i*N+j
      gcd[key]=math.gcd(i,j)
  
  for k, i in gcd.items():
    for j in range(1, N+1):
      key=j*N+i
      ans+=gcd[key]
        
  print(ans)
 
if __name__=='__main__':
  main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(set(A))
if N % 2 == 0 :
    for b in B :
        if b % 2 != 1 :
            ans = 0
            break
        elif A.count(b) != 2 :
            ans = 0
            break
    else :
        ans = 2**len(B)
else :
    for b in B :
        if b == 0 :
            if A.count(b) != 1 :
                ans = 0
                break
        elif b % 2 != 0 :
            ans = 0
            break
        elif A.count(b) != 2 :
            ans = 0
            break
    else :
        ans = 2**(len(B)-1)

print(ans)


### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
M = sorted(L,reverse=True)
flag = 1
for i in range(N) :
    if i % 2 == 0 :
        l = M[i]
        if l != (N-i-1) :
            flag = 0
            break
    else :
        if M[i] != l :
            flag = 0
            break
if flag == 0 :
    ans = 0
else :
    ans = (2**(N//2)) % (10**9+7)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
solve_problem = []
d = {i: 0 for i in range(1, N+1)}
ans = 0
penalty = 0
for i in range(M):
    p, S = input().split()
    if S == 'AC' and p not in solve_problem:
        solve_problem.append(p)
        ans += 1
        penalty += d[int(p)]
    if S == 'WA':
        d[int(p)] += 1

print('{} {}'.format(ans, penalty))



### FIXED CODE ###

N, M = map(int, input().split())
solve_problem = set()
WA = [0 for _ in range(N)]

ans = 0
penalty = 0

for i in range(M):
    p, S = input().split()
    if p in solve_problem:
        continue

    if S == 'AC':
        solve_problem.add(p)
        ans += 1
        penalty += WA[int(p)-1]
    if S == 'WA':
        WA[int(p)-1] += 1

print('{} {}'.format(ans, penalty))
### BUGGY CODE ###

from itertools import permutations

N, C = map(int, input().split())

D = [None] * C
for i in range(C):
    D[i] = list(map(int, input().split()))

c = [None] * N
for i in range(N):
    c[i] = list(map(int, input().split()))

ans = 10**12

# 塗り分けの順列総数
for p in permutations(range(C),3):
    tmp = 0
    for i in range(N):
        for j in range(N):
            tmp += D[c[i][j]-1][p[(i+j)%3]]
    ans = min(ans,tmp)

print(ans)

### FIXED CODE ###

from itertools import permutations

N, C = map(int, input().split())

D = [None] * C
for i in range(C):
    D[i] = list(map(int, input().split()))

c = [None] * N
for i in range(N):
    c[i] = list(map(int, input().split()))

# (i+j)%3 = 0,1,2 のそれぞれで初期マスの色をカウント
t = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        t[(i+j)%3][c[i][j]-1] += 1

ans = 10**12

# 塗り分けの順列総数
for p in permutations(range(C),3):
    tmp = 0
    for i in range(C):
        tmp += D[i][p[0]] * t[0][i]
        tmp += D[i][p[1]] * t[1][i]
        tmp += D[i][p[2]] * t[2][i]
    ans = min(ans,tmp)

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

from collections import deque

H, W = map(int, input().split())

INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
a = [input() for i in range(H)]

dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque([])
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            q.append([i, j, 0])

def update(c_h, c_w, d_map, dist, q):
    if d_map[c_h][c_w] != INF:
        return
    d_map[c_h][c_w] = dist
    for dir in range(4):
        if c_h+n_i[dir] < 0 or H <= c_h+n_i[dir] or c_w+n_j[dir] < 0 or W <= c_w+n_j[dir]:
            continue
        if a[c_h+n_i[dir]][c_w+n_j[dir]] == "#":
            continue
        q.append((c_h+n_i[dir], c_w+n_j[dir], dist+1))

while len(q) > 0:
    current = q.popleft()
    current_h = current[0]
    current_w = current[1]
    dist = current[2]
    update(current_h, current_w, dist_map, dist, q)

max_dist = 0
for i in range(H):
    for j in range(W):
        if max_dist < dist_map[i][j] and dist_map[i][j] != INF:
            max_dist = dist_map[i][j]
print(max_dist)


### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)
### BUGGY CODE ###

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

i=0
while True:
    if len(p)==1:
        break
    if p[i]<=p[i+1]:
        i+=1
    else:
        a=p[i]
        p[i]=p[i+1]
        p[i+1]=a
        i=0
    if i==len(p)-1:
        break

ans=0
for i in range(k):
    ans+=p[i]
print(ans)


### FIXED CODE ###

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

ans=0
if n!=1:
    for i in range(k):
        min=p[i]
        for j in range(i+1,n):
            if min>p[j]:
                min=p[j]
                p[j]=p[i]
                p[i]=min
        ans+=min
else:
    ans=p[0]
print(ans)