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

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

dp=[ [] for i in range(N+1) ]
dp[0]=[1]

mod=10**9+7


for n in range(N):
	W=[0]		#WA:累積和
	L=dp[n]
	l=len(L)
	a=A[n]
	for j,x in enumerate(L):
		if j==0:	W.append(x)
		else:	W.append( W[-1]+x )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )

	dp[n+1]=T



try:
	print dp[N][K]%mod
except IndexError:
	print 0

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0
### BUGGY CODE ###

import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    dx=V2[0]-V1[0]; dy=V2[1]-V1[1]
    sum_r=V1[2]+V2[2]
    return max(0,(dx**2+dy**2)**0.5-sum_r)

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i==j:
            continue
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
print(dijkstra(0,Edges)[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])
### BUGGY CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  for i in range(len(a)):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < len(a):
      ret[end+1] -= 1
  for i in range(1,len(a)):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)

### FIXED CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)
### BUGGY CODE ###

import itertools
n=int(input())
ss=input()
l=["R","G","B"]
ans=0
for v in itertools.permutations(l, 3):
    for i in range(n-2):
        if ss[i]==v[0]:
            for k in range(i+1,n-1):
                if ss[k]==v[1]:
                    ans+=ss[k+1:].count(v[2])
                    if (k+k-i <=n-1) and ss[k+k-i]==v[2]:
                        ans-=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=s.count("R")*s.count("G")*s.count("B")  # 第１条件の全事象
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+j-i
        if k<n and s[k]!=s[i] and s[k]!=s[j] and s[i]!=s[j]: # 第1条件 かつ not第２条件
            ans-=1
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(int(i) for i in input().split()) 
n = N//2
cnt = 0
data = sorted(L)
data1 = data[:n]
data2 = data[n:]
for i in range(100000):
    if max(data1) < i and i <= min(data2):
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
L = list(int(i) for i in input().split()) 
n = N//2
data = sorted(L)
data1 = data[:n]
data2 = data[n:]
print(min(data2) - max(data1))
### BUGGY CODE ###

from collections import defaultdict


def main():
    K, S = map(int, input().split())
    ans = 0
    for x in range(0, K + 1):
        for y in range(0, K + 1):
            for z in range(0, K + 1):
                ans += (x + y + z == S)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict


def main():
    K, S = map(int, input().split())
    ans = 0
    for x in range(0, K + 1):
        for y in range(0, K + 1):
            if 0 <= S - (x + y) <= K:
                ans += 1
    print(ans)


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

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        t = deque(list((map(lambda x: int(x) - 1, input().split()))))
        A.append(t)

    res = 0
    emp = [1] * n
    while True:
        check = [0] * n
        for i in range(n):
            if A[i] and not check[i]:
                idx = A[i][0]
                if not check[idx] and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    check[i] = check[idx] = 1
            if not A[i]:
                emp[i] = 0
        res += 1
        if sum(emp) == 0:
            break
        if sum(check) == 0:
            print(-1)
            exit()
    print(res)





if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        t = deque(list((map(lambda x: int(x) - 1, input().split()))))
        A.append(t)

    que = deque(list(range(n)))
    res = 0
    emp = [False] * n
    while que:
        next_que = deque([])
        check = set()
        while que:
            i = que.popleft()
            if A[i]:
                idx = A[i][0]
                if i not in check and idx not in check and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    next_que.append(i)
                    next_que.append(idx)
                    check.add(i)
                    check.add(idx)
            else:
                emp[i] = True
        que = next_que
        if que:
            res += 1
    else:
        print(res if all(emp) else -1)


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

n = int(input())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[j] + l[k] > l[i]:
                cnt += 1
            else:
                break

print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        x = bisect.bisect_left(l, l[i]+l[j])
        cnt += x-j-1

print(cnt)
### BUGGY CODE ###

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

def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

resi = []
for j in range(n):
	if j == 0:
		res = ai[1]
		for i in range(2,n):
			res = gcd(ai[i],res)
	else:
		res = ai[0]
		for i in range(1,n):
			if i == j:
				continue
			else:
				res = gcd(ai[i],res)
	resi.append(res)

#print(resi)
print(max(resi))


### FIXED CODE ###

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

def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

r=[]
l=[]
resr = ai[0]
resl = ai[n-1]
r.append(ai[0])
l.append(ai[n-1])
for i in range(1,n):
	resr=gcd(resr,ai[i])
	r.append(resr)
	resl=gcd(resl,ai[n-1-i])
	l.append(resl)

#print(r)
#print(l)

resmax = 1
for i in range(n):
	if i == 0:
		res = l[n-1-1]
	elif i == n-1:
		res = r[n-1-1]
	else:
		res = gcd(r[i-1], l[n-1-i-1])
	if res > resmax:
		resmax = res

print(int(resmax))
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
if n == 1:
    print(0)
else:
    point = 0
    for i in range(1,n):
        point += i
    print(point)

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
point = n*(n-1)//2
print(point)
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
cnt = N
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    if A[j] > A[i]:
      break
    if A[i] % A[j] == 0:
      cnt -= 1
      break
print(cnt)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]
B = [0] * m
for a in A:
  B[a - 1] += 1
  if B[a - 1] == 1:
    for j in range(a * 2, m + 1, a):
      B[j - 1] = 2
print(B.count(1))
### BUGGY CODE ###

import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

### FIXED CODE ###

from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(n-2):
    one = s[i]
    for j in range(i+1,n-1):
        if one == s[j]:
            continue
        two = s[j]
        l = j-i
        for k in range(j+1,n):
            if s[k] != one and s[k] != two:
                if k-j != l:
                    ans += 1

print(ans)



### FIXED CODE ###

n = int(input())
s = input()
 
ans = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    for j in range(i+1,n-1):
        k = 2*j-i
        if k < n:
            if s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
                    ans -= 1
                    
print(ans)
### BUGGY CODE ###

import string

alpha = 'abcdefghijklmnopqrstuvwxyza'
tbl = string.maketrans(alpha[:-1], alpha[1:])

while True:
	sentence = raw_input()
	while 'the' not in sentence or 'that' not in sentence or 'this' not in sentence:
		sentence = sentence.translate(tbl)

	print sentence

### FIXED CODE ###

import string, sys

alpha = 'abcdefghijklmnopqrstuvwxyza'
tbl = string.maketrans(alpha[:-1], alpha[1:])

for s in sys.stdin:
	while not('the' in s or 'that' in s or 'this' in s):
		s = s.translate(tbl)
	print s[:-1]
### BUGGY CODE ###

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

g = [[] for _ in range(h*w)]
for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    g[idx1].append(idx2)

ans = 0
for i in range(h*w):
    s = []
    s.append(i)
    visit = [-1]*(h*w)
    visit[i] = 0
    while s:
        v = s.pop()
        for  u in g[v]:
            if visit[u] == -1:
                visit[u] = visit[v]+1
                if visit[u]%2 == 1:
                    ans += 1
                s.append(u)
print(ans//2)


### FIXED CODE ###

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

#g = [[] for _ in range(h*w)]

n = h*w

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

for y in range(h):
    for x in range(w):
        idx1 = y*w+x
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                idx2 = ny*w+nx
                if S[y][x] != S[ny][nx]:
                    Unite(idx1, idx2, par, rank)

ans = 0
#print(par)
X = [[0, 0] for _ in range(n)]
K = []

for i in range(n):
    y, x = divmod(i, w)
    if par[i] < 0:
        K.append(i)
        if S[y][x] == '#':
            X[i][0] += 1
        else:
            X[i][1] += 1
    else:
        if S[y][x] == '#':
            X[Find(i, par)][0] += 1
        else:
            X[Find(i, par)][1] += 1

ans = 0
for k in K:
    ans += X[k][0]*X[k][1]
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

# a, bをfixしてcを探索
# n*n*logn
# c_i < a+b をにぶたん
def binary_search(list, item):
    # listからitem未満の最大のindexを取得
    low = 0
    high = len(list) - 1
    if list[high] < item:
        return high+1
    if list[low] >= item:
        return low
    while True:
        mid = (low + high) //2
        guess = list[mid]
        if high - low <= 1:
            return high
        if guess >= item:
            high = mid
        else:
            low = mid

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        a = l[i]
        b = l[j]
        c = binary_search(l, b+a)
        ans += c-(j+1)
print(ans)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

# a, bをfixしてcを探索
# n*n*logn
# c_i < a+b をにぶたん
def binary_search(list, item):
    # listからitem未満の最大のindexを取得
    low = 0
    high = len(list) - 1
    if list[high] < item:
        return high+1
    if list[low] >= item:
        return low
    while True:
        mid = (low + high) //2
        guess = list[mid]
        if high - low <= 1:
            return high
        if guess >= item:
            high = mid
        else:
            low = mid

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        a = l[i]
        b = l[j]
        c = binary_search(l, b+a)
        ans += c-(j+1)
print(ans)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
ret = []
for i in range(1,n+1):
  ret.append([k+1 for k, x in enumerate(L) if x == i])
print(*sum(ret,[]))

### FIXED CODE ###

n = int(input())
L = list(map(int, input().split()))
ret = []
L = sorted(range(len(L)), key=lambda k: L[k])
print(*map(lambda x: x+1, L))
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
ans=1
if x.count(0)>=18:
  print(-1)
  exit()
  
for i in x:
  ans=ans*i
  if ans>10**18:
    ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
ans=1
for i in x:
  if i==0:
    print(0)
    exit()

for i in x:
    ans=ans*i
    if ans>10**18:
      ans=-1
      break
print(ans)
### BUGGY CODE ###

import os, sys, re, math

N = int(input())
A = [int(n) for n in input().split()]

sa = ''
for s in sorted(A):
    sa += '%s ' % (A.index(s) + 1)
print(sa.strip())

### FIXED CODE ###

import os, sys, re, math

N = int(input())
A = [int(n) for n in input().split()]

ta = [(A[i], i + 1) for i in range(N)]
sa = sorted(ta, key=lambda k: k[0])

result = ''
for s in sa:
    result += '%s ' % s[1]
print(result.strip())
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
# print(w)
# print(v)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
# print(dp)
# dp loop
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
# print(dp)
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
# print(w)
# print(v)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
# print(dp)
# dp loop
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
# print(dp)
print(dp[N][W])
### BUGGY CODE ###

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0

while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1

print(-1)

### FIXED CODE ###

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)
### BUGGY CODE ###

from itertools import combinations as comb

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

min=None
for x in comb(range(n),k):
    sm=0
    for i in range(len(x)):
        sm+=p[x[i]]
    if not min : min=sm
    if sm<min : min=sm
print(min)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
sm=sum(p[:k])
print(sm)
### BUGGY CODE ###

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

lis = []

for i in set(a):
    if 2 <= a.count(i) <= 3:
        lis.append(i)
    elif 4 <= a.count(i):
        lis.append(i)
        lis.append(i)


lis.sort(reverse=True)
if len(lis) <= 1:
    ans = 0
else:
    ans = lis[0]*lis[1]

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from collections import Counter
a = Counter(a)
lis = []

for i,j in a.items():
    lis += [i]*(j//2)

#print(lis)

lis.sort(reverse=True)
if len(lis) <= 1:
    ans = 0
else:
    ans = lis[0]*lis[1]

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

#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


# %%
import numpy as np
from scipy.optimize import fmin


# %%
N, K = map(int, readline().split())
XYZ = np.array(read().split(), np.int64)
X = XYZ[::3]
Y = XYZ[1::3]
Z = XYZ[2::3]

# %%


def f(pt):
    x, y = pt
    cost = Z * ((x - X) ** 2 + (y - Y) ** 2) ** .5
    cost.sort()
    return cost[K - 1]


def calc(x0):
    opt_pt = fmin(f, x0, disp=False, ftol=1e-7)
    return f(opt_pt)


# %%
answer = 10 ** 18
for x, y, z in zip(X, Y, Z):
    f_value = calc([x, y])
    if answer > f_value:
        answer = f_value
    for n in np.random.randint(0, N, 2):
        x1, y1, z1 = X[n], Y[n], Z[n]
        f_value = calc([(x * z1 + x1 * z) / (z + z1), (y * z1 + y1 * z) / (z + z1)])
        if answer > f_value:
            answer = f_value

# %%
print(answer)


# %%


### FIXED CODE ###

import sys
from cmath import rect
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

eps = 1e-9

@njit((numba.complex128, numba.float64) * 2, cache=True)
def cross_circles(c1, r1, c2, r2):
    d = abs(c1 - c2)
    if d <= abs(r1 - r2) or r1 + r2 <= d:
        return None
    cos_theta = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d)
    theta = np.arccos(cos_theta)
    z1 = (c2 - c1) * rect(r1 / d, theta)
    z2 = (c2 - c1) * rect(r1 / d, -theta)
    return (c1 + z1, c1 + z2)

@njit
def test(Z, C, t):
    R = t / C
    cand = list(Z)
    for j in range(len(Z)):
        for i in range(j):
            points = cross_circles(Z[i], R[i], Z[j], R[j])
            if points is not None:
                for p in points:
                    cand.append(p)
    cand = np.array(cand)
    cnt = np.zeros(len(cand), np.int64)
    for i in range(len(Z)):
        cnt += np.abs(cand - Z[i]) <= R[i] + eps
    return np.any(cnt >= K)

N, K = map(int, readline().split())
nums = np.array(read().split(), np.float64)

Z = nums[::3] + 1j * nums[1::3]
C = nums[2::3]

l = 0
r = 10**9
for _ in range(100):
    m = (l + r) / 2
    if test(Z, C, m):
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

N,M=map(int,input().split())
cake=[list(map(int,input().split()))for _ in[0]*N]
dp=[[[0]*3]for _ in[0]*(M+1)]
for c in cake:
    for i in range(M-1,-1,-1):
        for t in dp[i]:
            dp[i+1]+=[[c[i]+t[i]for i in range(3)]]
print(max(sum(map(abs,x))for x in dp[M]))

### FIXED CODE ###

N,M=map(int,input().split())
sums=[[]for _ in[0]*8]
for _ in[0]*N:
    c=list(map(int,input().split()))
    for t in range(8):
        sums[t]+=[sum(c[i]*[-1,1][t&(1<<i)>0]for i in range(3))]
if M:print(max(sum(sorted(sums[i])[-M:])for i in range(8)))
else:print(0)
### BUGGY CODE ###

import fractions


def lcm_list(numbers):
    ans = numbers[0]
    for number in numbers[1:]:
        ans = (((number * ans)) //(fractions.gcd(number, ans)))
    return ans


MOD = 10 ** 9 + 7
N = input()
i = 0
arrs = list(map(int, input().split()))
lcms = lcm_list(arrs)
result = 0
for arr in arrs:
    result = (result + (lcms // arr)) % MOD
print(result)

### FIXED CODE ###


from fractions import gcd
MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
result = 0
lcms = 1
for number in arrs:
    lcms = (((number * lcms)) //(gcd(number, lcms)))
for arr in arrs:
    result += (lcms//arr)
result = result%MOD
ans = str(result).replace('.0','')
print(ans)