Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

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

for a,b in AB:
    lst[a].append(b)
    lst[b].append(a)



used=set(list(range(1,N+1)))
value=-10**18
while used:
    a=used.pop()
    stack=[a]

    visited={a}
    while stack:
        a=stack.pop()
        for p in lst[a]:
            if not p in visited:
                visited.add(p)
                stack.append(p)
    value=max(len(visited),value)
print(value)


Fixed submission:
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

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

for a,b in AB:
    lst[a].append(b)
    lst[b].append(a)



used=set(list(range(1,N+1)))
value=-10**18
while used:
    a=used.pop()
    stack=[a]

    visited={a}
    while stack:
        a=stack.pop()
        for p in lst[a]:
            if p in used:
                used.remove(p)
            if not p in visited:
                visited.add(p)
                stack.append(p)
    value=max(len(visited),value)
print(value)
Buggy python submission (verdict: Runtime Error):
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
A=[soinsuu(a) for a in A]
visited=set()
flg=False
for a in A:
    for i in a:
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

n=a[0]
for a in A[1:]:
    n=gcd(n,a)



if n>1:
    print("not coprime")
else:
    print("setwise coprime")


Fixed submission:
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
visited=set()
flg=False
for a in A:
    for i in soinsuu(a):
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

n=A[0]
for a in A[1:]:
    n=gcd(n,a)



if n>1:
    print("not coprime")
else:
    print("setwise coprime")

Buggy python submission (verdict: Runtime Error):
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
A=[soinsuu(a) for a in A]
visited=set()
flg=False
for a in A:
    for i in a:
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

visited=soinsuu(A[0])
for a in A[1:]:
    for i in a:
        visited[i]-=data[i]

if [i for i in visited if visited[i]>0]:
    print("not coprime")
else:
    print("setwise coprime")


Fixed submission:
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
visited=set()
flg=False
for a in A:
    for i in soinsuu(a):
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

n=A[0]
for a in A[1:]:
    n=gcd(n,a)



if n>1:
    print("not coprime")
else:
    print("setwise coprime")
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()



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


def main(n):
    return(sum([max(i//n-(i%n==0)*1,0) for i in A])<=K)
#print(main(5))
ng=0
ok=10**18
while ok-ng>1:
    mid=(ok+ng)//2
    if main(mid):
        ok=mid
    else:
        ng=mid

print(ok)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()



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


def main(n):
    return(sum([max(i//n-(i%n==0)*1,0) for i in A])<=K)
#print(main(5))
ng=0
ok=10**18
while ok-ng>1:
    mid=(ok+ng)//2
    if main(mid):
        ok=mid
    else:
        ng=mid

print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
#N=10**18
if N==1:
    print(0)
    exit()

i=2
#N=10**12
def sosuu(x):
    sosuulst=[]
    i=2
    while i<int(x**.5+1):
        for s in sosuulst:
            if i%s==0:
                break
        else:
            sosuulst.append(i)
        i+=1
    for s in sosuulst:
        if x%s==0:
            while x%s==0:
                x//=s
            if x==1:
                return(1)
            else:
                return(0)
    return(1)


c=0
lst=[]
lst2=[]
for i in range(2,int(N**.5+1)):
    if N%i==0:
        lst.append(i)
        lst2.append(N//i)
lst2.reverse()
lst+=lst2
lst.append(N)
#print(lst)
for i in lst:

    if N%i==0:

        if sosuu(i):
        #    print(N,i)
            N//=i
            c+=1
print(c)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
#N=10**18

lst=defaultdict(int)
lst2=[]
lst3=[]
for i in range(2,int(N**.5)+100):
    if N%i==0:
        lst2.append(i)
        lst3.append(N//i)
lst3.reverse()
lst2+=lst3

for i in lst2+[N]:
    while N>1 and N%i==0:
        N//=i
        lst[i]+=1
c=0
#print(lst)
for s in lst:
    l=lst[s]
    i=1
    while l>=i:
        l-=i
        c+=1
        i+=1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
st=1
ed=N
C=max(main(st),main(ed))
while ed-st>2:
    #print(ed,st)
    mid1=(st*2+ed)//3
    mid2=(st+ed*2)//3
    C0=main(st)
    C1=main(mid1)
    C2=main(mid2)
    C3=main(ed)
    C=max(C,C0,C1,C2,C3)
    if C0==C:
        ed=mid2
    elif C1==C:
        ed=mid2
    elif C2==C:
        st=mid1
    elif C3==C:
        st=mid1
if ed-st==2:
    C=max(main(st),main(st+1),main(ed),C)
print(C)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main2(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(A*x//B-A*(x//B))

if N>=B-1:
    Z=B-1
else:
    Z=N
print((main2(Z)))

#print(C)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
c=-(10**18)
for x in range(1,N+1):
    c=max(c,main(x))
print(c)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main2(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(A*x//B-A*(x//B))

if N>=B-1:
    Z=B-1
else:
    Z=N
print((main2(Z)))

#print(C)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
S=list(reversed(input()))
lst=[0 for i in range(len(S))]
num=0
z=1
for i in range(len(S)):
    num+=int(S[i])*z
    num%=2019
    z*=10
    lst[i]=num
lst=Counter(lst)
lst[0]+=1
count=0
for l in lst:
    n=lst[l]
    count+=n*(n-1)//2
print(count)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
S=list(reversed(input()))
lst=[0 for i in range(len(S))]
num=0
z=1
for i in range(len(S)):
    num+=int(S[i])*z
    num%=2019
    z*=10
    z%=2019
    lst[i]=num
lst=Counter(lst)
lst[0]+=1
count=0
for l in lst:
    n=lst[l]
    count+=n*(n-1)//2
print(count)
Buggy python submission (verdict: Runtime Error):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort()
c=0
for i in range(N//2):
    a1,i1=A.pop()
    a2,i2=A.pop()
    b=(N-1-i)
    c+=max(a1*round(abs(i-i1))+a2*round(abs(b-i2)),a1*round(abs(b-i1))+a2*round(abs(i-i2)))
if N%2:
    a1,i1=A.pop()
    b=(N-1)//2
    c+=ai*round(abs(b-i1))
print(c)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(reverse=True)
dp=[[0 for i in range(N+1)] for _ in range(N+1)]
for n in range(N):
    a,p=A[n]
    for x in range(1,n+2):
        y=n+1-x
        dp[x][y]=max(dp[x][y],dp[x-1][y]+round(abs(x-1 - p))*a)
    for y in range(1,n+2):
        x=n+1-y
        dp[x][y]=max(dp[x][y],dp[x][y-1]+round(abs(N-y - p))*a)
    #print(dp)
print(max([dp[x][y] for x in range(N+1) for y in range(N+1) if x+y==N]))

Buggy python submission (verdict: Runtime Error):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort()
c=0
for i in range(N//2):
    a1,i1=A.pop()
    a2,i2=A.pop()
    b=(N-1-i)
    c+=max(a1*round(abs(i-i1))+a2*round(abs(b-i2)),a1*round(abs(b-i1))+a2*round(abs(i-i2)))
if A:
    a1,i1=A.pop()
    b=(N-1)//2
    c+=ai*round(abs(b-i1))
print(c)


Fixed submission:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(reverse=True)
dp=[[0 for i in range(N+1)] for _ in range(N+1)]
for n in range(N):
    a,p=A[n]
    for x in range(1,n+2):
        y=n+1-x
        dp[x][y]=max(dp[x][y],dp[x-1][y]+round(abs(x-1 - p))*a)
    for y in range(1,n+2):
        x=n+1-y
        dp[x][y]=max(dp[x][y],dp[x][y-1]+round(abs(N-y - p))*a)
    #print(dp)
print(max([dp[x][y] for x in range(N+1) for y in range(N+1) if x+y==N]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
K=int(input())
#A,B=map(int,input().split())
#A=list(map(int,input().split()))
z=0
for a in range(1,K+1):
    for b in range(1,K+1):
        d=gcd(a,b)
        if d==1:
            z+=K
        else:
            for c in range(1,K+1):
                z+=gcd(c,d)
print(z)


Fixed submission:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
K=int(input())
#A,B=map(int,input().split())
#A=list(map(int,input().split()))
z=0
dic=defaultdict(int)
for a in range(1,K+1):
    for b in range(1,K+1):
        d=gcd(a,b)
        dic[d]+=1
for d in dic:

    for c in range(1,K+1):
        z+=dic[d]*gcd(c,d)
print(z)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
K=int(input())
#A,B=map(int,input().split())
#A=list(map(int,input().split()))
z=0
for a in range(1,K+1):
    for b in range(1,K+1):
        d=gcd(a,b)
        for c in range(1,K+1):
            z+=gcd(c,d)
print(z)


Fixed submission:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
K=int(input())
#A,B=map(int,input().split())
#A=list(map(int,input().split()))
z=0
dic=defaultdict(int)
for a in range(1,K+1):
    for b in range(1,K+1):
        d=gcd(a,b)
        dic[d]+=1
for d in dic:

    for c in range(1,K+1):
        z+=dic[d]*gcd(c,d)
print(z)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()


N,X,Y=map(int,input().split())
data=[[] for i in range(N+1)]
for i in range(1,N):
    a=i;b=i+1
    data[a].append(b)
    data[b].append(a)
data[X].append(Y)
data[Y].append(X)


dic=defaultdict(int)
for n in range(1,N+1):
    stack=deque([[n,0]])
    visited=set()
    while stack:
        #print(stack)
        a,m=stack.popleft()
        for p in data[a]:
            if not p in visited:
                visited.add(p)
                stack.append([p,m+1])
                if p>n:
                    dic[m+1]+=1


lst=[]
for i in range(N-1):
    print(dic[i+1])


Fixed submission:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()


N,X,Y=map(int,input().split())
data=[[] for i in range(N+1)]
for i in range(1,N):
    a=i;b=i+1
    data[a].append(b)
    data[b].append(a)
data[X].append(Y)
data[Y].append(X)


dic=defaultdict(int)
for n in range(1,N+1):
    stack=deque([[n,0]])
    visited=set()
    while stack:
        #print(stack)
        a,m=stack.popleft()
        for p in data[a]:
            if not p in visited:
                visited.add(p)
                stack.append([p,m+1])
                if p>n:
                    dic[m+1]+=1


lst=[]
for i in range(N-1):
    print(dic[i+1])
Buggy python submission (verdict: Runtime Error):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

#A=list(map(int,input().split()))
#XY=[list(map(int,input().split())) for i in range(N)]

a,b,c=map(int,input().split())
X=gcd(gcd(a,b),c)
c//=X
a//=X
b//=X

if math.isclose(c**.5,a**.5+b**.5):
    print("No")

elif c**.5-a**.5-b**.5>0.0:
    print("Yes")
else:
    print("No")


Fixed submission:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
from decimal import *
#input = sys.stdin.readline


#N=int(input())

#A=list(map(int,input().split()))
#XY=[list(map(int,input().split())) for i in range(N)]

a,b,c=map(int,input().split())
X=gcd(gcd(a,b),c)
c//=X
a//=X
b//=X
getcontext().prec = 500
c=Decimal(c).sqrt()
b=Decimal(b).sqrt()
a=Decimal(a).sqrt()

if c-a-b>0.0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd"""

N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
#visited=set()
for n,s in enumerate(S):
    s=int(s)
    for i in range(P):
        A=(i*10+s)%P
        dp[n][A]+=dp[n-1][i]
    dp[n][s%P]+=1


count=0
for i in dp:
    count+=i[0]
print(count)


Fixed submission:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd


mod=10**9+7
N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
visited=set()
nset=set()
for n,s in enumerate(S):
    s=int(s)%P
    if nset:
        nset.clear()
    for i in visited:#range(P):
        A=(i*10+s)%P
        if dp[n-1][i]:
            nset.add(A)
            dp[n][A]+=dp[n-1][i]

    dp[n][s]+=1
    visited.add(s)
    visited=visited|nset
print(sum([i[0] for i in dp]))


Fixed submission:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

mod=10**9+7
N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
#visited=set()
for n,s in enumerate(S):
    s=int(s)
    for i in range(P):
        A=(i*10+s)%P
        dp[n][A]+=dp[n-1][i]
    dp[n][s%P]+=1

print(sum([i[0] for i in dp]))


Fixed submission:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)
Buggy python submission (verdict: Runtime Error):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math

def get_circle_center_and_radius(x1, y1, x2, y2, x3, y3):
    """
    3点を通る円の中心と半径を取得
    """
    d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
    if d==0:
        return(0)
    x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) - (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
    y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) - (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
    #r = math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
    return (x, y)
#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
N,K=map(int,input().split())
XYC=[list(map(int,input().split())) for i in range(N)]
if K==1:
    print(0)
    exit()
count=10**18

if N>=2:
    nlst=combinations(list(range(N)),2)

    for n1,n2 in nlst:
        x1,y1,c1=XYC[n1]
        x2,y2,c2=XYC[n2]
        A=c1+c2
        X=(x1*c1+x2*c2)/A
        Y=(y1*c1+y2*c2)/A
        count1=[]
        for x,y,c in XYC:
            count1.append(((X-x)**2+(Y-y)**2)**0.5*c)
        count1.sort()
        #print(X,Y,count1)
        count=min(count,count1[K-1])

if N>=3:
    nlst=combinations(list(range(N)),3)
    for n1,n2,n3 in nlst:
        x1,y1,c1=XYC[n1]
        x2,y2,c2=XYC[n2]
        x3,y3,c3=XYC[n3]
        C=get_circle_center_and_radius(c1*x1,c1*y1,c2*x2,c2*y2,c3*x3,c3*y3)
        if C:
            X,Y=C
        else:
            continue
        X,Y=X/A,Y/A

        count1=[]
        for x,y,c in XYC:
            count1.append(((X-x)**2+(Y-y)**2)**0.5*c)
        count1.sort()

        count=min(count,count1[K-1])

print(count)


Fixed submission:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#import math

#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]

N=int(input())
print(N//2+N%2)