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

# -*- coding: utf-8 -*-
import sys
from itertools import permutations

i = sys.stdin
N, C = map(int, i.readline().strip().split())
D = [[int(_) for _ in i.readline().strip().split()] for c in range(C)]
G = [[int(_) for _ in i.readline().strip().split()] for n in range(N)]

table = [[0 for c in range(C)] for _ in range(3)]
for c in range(C):
    for row in range(N):
        for col in range(N):
            table[(row + col) % 3][c] += D[G[row][col] - 1][c]

cst = 1000 * 500**2
combs = permutations(range(C), 3)
for comb in combs:
    cst = min(cst, table[0][comb[0]] + table[1][comb[1]] + table[2][comb[2]])

print(cst)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, C = map(int, input().split())

D = []
for c in range(C):
    D.append([int(d) for d in input().split()])

Gmod = [[0 for i in range(C)] for i in range(3)]
for n in range(N):
    for m, g in enumerate(input().split()):
        Gmod[(n + m) % 3][int(g) - 1] += 1

K = []
for c0 in range(C):
    d0 = sum([Gmod[0][c] * D[c][c0] for c in range(C)])
    for c1 in [i for i in range(C) if not i == c0]:
        d1 = sum([Gmod[1][c] * D[c][c1] for c in range(C)])
        for c2 in [i for i in range(C) if (not i == c0) and (not i == c1)]:
            d2 = sum([Gmod[2][c] * D[c][c2] for c in range(C)])
            K.append(d0 + d1 + d2)

print(min(K))
### BUGGY CODE ###

def solve(N, K, cards):
  min_elem = cards[0]

  TARO, JIRO = 0, 1
  dp = [[-1 for _ in range(K + 1)] for _ in range(2)]

  dp[TARO][0] = TARO
  dp[JIRO][0] = JIRO

  for i in range(min_elem):
    dp[JIRO][i] = TARO
    dp[TARO][i] = JIRO

  for k in range(1, K + 1):
    for turn in [TARO, JIRO]:
      opp = JIRO if turn == TARO else TARO
      dp[turn][k] = opp
      for c in cards:
        if c > k:
          break
        if k - c == 0:
          dp[turn][k] = turn
          break
        if k - c > 0 and dp[opp][k - c] == turn:
          dp[turn][k] = turn

  print("First" if dp[TARO][K] == TARO else "Second")

  
def iln(): return list(map(int, input().split()))


N, K = iln()
cards = iln()
solve(N, K, cards)

### FIXED CODE ###

def solve(N, K, cards):
  min_elem = cards[0]

  # dp[i] == True: Current player will win if i stones left
  dp = [False for _ in range(K + 1)]
  for i in range(min_elem):
    dp[i] = False

  for k in range(1, K + 1):
    for c in cards:
      if c > k:
        break
      if k - c >= 0 and dp[k - c] == False:
        dp[k] = True

  print("First" if dp[K] else "Second")

  
def iln(): return list(map(int, input().split()))


N, K = iln()
cards = iln()
solve(N, K, cards)
### BUGGY CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b
for i in range(1, (n // 2) + 1):
    for j in range(0, n - (2 * i) + 1):
        if j + (2 * i) >= n:
            break
        if ((s[j] != s[j + i]) & (s[j] != s[j + (2 * i)]) & (s[i + j] != s[j + (2 * i)])):
            ans -= 1
        
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = n - r - g

ans = r * g * b
for i in range(1, (n // 2) + 1):
    for j in range(0, n - (2 * i) + 1):
        if j + (2 * i) >= n:
            break
        if ((s[j] != s[j + i]) & (s[j] != s[j + (2 * i)]) & (s[i + j] != s[j + (2 * i)])):
            ans -= 1
        
print(ans)
### BUGGY CODE ###

import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    x = input()
    le = len(x)
    while True:
        bit = 0
        for i in range(le-1):
            if x[i:i+2] == "ST":
                x = x[0:i]+x[i+2:le]
                bit = 1
                break
        if bit == 0:
            print(len(x))
            break

    return 0
 
if __name__ == "__main__":
    solve()


### FIXED CODE ###

import numpy as np
import functools
import math
import scipy
import fractions
import itertools
 
def solve():
    x = input()
    a, b = 0, 0
    for i in x:
        if i == "S":
            a += 1
        else:
            if a == 0:
                b += 1
            else:
                a -= 1
    print(a + b)
    return 0

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

n=int(input())
a=[]
for i in range(n):
    b=input()
    a.append(b)
b=n-1
c=0
for i in range(n-1):
    d=a.count(a[b])
    if d==1:
        b-=1
    else:
        del a[b]
        b-=2
print(len(a))


### FIXED CODE ###

n=int(input())
a=set()
for i in range(n):
    b=input()
    a.add(b)
print(len(a))
### BUGGY CODE ###

S=input()
l=len(S)
num=int(S)
# print(l,num,S)
count=0
for _ in reversed(range(l)):
    # print(_,(_%2==1)*1,num//(10**_))
    if num//(10**_)!=(_%2==1)*1:
        count+=1
    num=num%(10**_)
    # print(count)

print(min(count,l-count))
    

### FIXED CODE ###

s=input()
l=len(s)

suuti=[]
for _ in s:
    suuti.append(int(_))

rei=[]
for _ in range(l):
    rei.append(_%2)

c=0
for _ in range(l):
    if rei[_]==suuti[_]:
        c+=1

print(min(c,l-c))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  dic[i+1]=a[i]

dic2 = sorted(dic.items(), key=lambda x:x[1])

ans=""
for i in dic2:
  ans=ans+str(i[0])+" "
  
  
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  dic[i+1]=a[i]
 
dic2 = sorted(dic.items(), key=lambda x:x[1])
 
ans=""
for i in dic2:
  print(i[0],end=" ")
  
  
  
print(ans)
### BUGGY CODE ###

"""メモリ足りねぇ..."""

import sys
pin=sys.stdin.readline

INF=10**10
N,W=map(int,pin().split())

dp=[[INF]*100001 for _ in [0]*(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  w,v=pin().split()
  w=int(w)
  v=int(v)
  for j in range(100001):
    if j-v>=0:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v]+w)
    else:
      dp[i][j]=dp[i-1][j]
ans=100000
while dp[N][ans]>W:
  ans-=1
print(ans)
#解説AC

### FIXED CODE ###

"""メモリ足りねぇ..."""

import sys
pin=sys.stdin.readline

INF=10**10
N,W=map(int,pin().split())

dp=[[INF]*100001 for _ in [0]*(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  w,v=pin().split()
  w=int(w)
  v=int(v)
  for j in range(100001):
    if j-v>=0:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v]+w)
    else:
      dp[i][j]=dp[i-1][j]
ans=100000
while dp[N][ans]>W:
  ans-=1
print(ans)
#解説AC
### BUGGY CODE ###

# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

N = int(input())
a = list(map(int, input().strip().split(" ")))

sum = 0
max = a[0]-1
min = a[0]-1
for i in range(N):
    a[i] = a[i] - (i+1)
    sum += a[i]
    if a[i] > max:
        max = a[i]
    if a[i] < min:
        min = a[i]

sadnesses = []

for b in range(min, max + 1):
    sadness = 0
    for i in range(N):
        if a[i] > b:
            sadness += a[i] - b
        else:
            sadness += b - a[i]
    sadnesses.append(sadness)

sadnesses.sort()
print(sadnesses[0])


### FIXED CODE ###

# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

N = int(input())
a = list(map(int, input().strip().split(" ")))

for i in range(N):
    a[i] = a[i] - (i+1)

a.sort()
if N % 2 != 0:
    mid = (N-1)//2
else:
    mid = N // 2 -1
b = a[mid]

sadness_left = b * mid - sum(a[:mid])
sadness = sum(a) - b * N + sadness_left * 2

print(sadness)
### BUGGY CODE ###

s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
#tem = [i%13 for i in range(130)]
tem = [[i*j%13 for i in range(10)] for j in range(13)]
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5])


### FIXED CODE ###

s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0

for i in range(k + 1):
    for j in range(k + 1):
        for h in range(k + 1):
            if h + i + j == s:
                ans += 1

print(ans)


### FIXED CODE ###

k, s = map(int, input().split())

ans = 0

for i in range(k + 1):
    for j in range(k + 1):
        z = s - i - j
        if 0 <= z <= k:
            ans += 1

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

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N = int(f_i.readline())
    A = list(map(int, f_i.readline().split()))
    A_max = max(A)
    
    ans = 0
    b = 1
    while A_max:
        next_A = []
        
        bit_cnt = 0
        
        for A_i in A:
            if A_i & 1:
                bit_cnt += 1
            A_i >>= 1
            if A_i:
                next_A.append(A_i)
        
        ans += b * bit_cnt * (N - bit_cnt)
        ans %= mod
        
        b *= 2
        A_max >>= 1
        A = next_A[:]
        
    print(ans)

solve()

### FIXED CODE ###

def solve():
    import numpy as np
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N = int(f_i.readline())
    A = np.array(f_i.readline().split(), dtype=np.int64)
    
    ans = 0
    for i in range(60):
        cnt = np.count_nonzero((A >> i) & 1)
        ans += (1 << i) * cnt * (N - cnt)
    
    print(ans % mod)

solve()
### BUGGY CODE ###

n,q=map(int,input().split())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)
ps=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ps[p-1]+=x

s=[-1 for i in range(n)]
sc=[0]
s[0]=0
while sc:
  nsc=[]
  for i in sc:
    s[i]+=ps[i]
    for j in e[i]:
      if s[j]==-1:
        nsc.append(j)
        s[j]=s[i]
  sc=nsc

r=""
for i in range(n):
  r+=str(s[i])+" "
print(r[:-1])

### FIXED CODE ###

n,q=map(int,input().split())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)
ps=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ps[p-1]+=x

s=[-1 for i in range(n)]
sc=[0]
s[0]=0
while sc:
  nsc=[]
  for i in sc:
    s[i]+=ps[i]
    for j in e[i]:
      if s[j]==-1:
        nsc.append(j)
        s[j]=s[i]
  sc=nsc

r=""
for i in range(n):
  r+=str(s[i])+" "
print(r[:-1])
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0

R = [0] * n
G = [0] * n
B = [0] * n

r = 0
g = 0
b = 0

for i in range(n):
    if s[i] == "R":
        r += 1
        R[i] = r
    elif s[i] == "G":
        g += 1
        G[i] = g
    else:
        b += 1
        B[i] = b

for i in range(n-2):
    for j in range(i+1,n-1):
        x = s[i]
        y = s[j]
        
        if x != y:
            if "R" not in [x,y]:
                ans += R[n-1] - R[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "R":
                        ans -= 1
                    
            if "G" not in [x,y]:
                ans += G[n-1] - G[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "G":
                        ans -= 1
                    
            if "B" not in [x,y]:
                ans += B[n-1] - B[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "B":
                        ans -= 1
    
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0

R = [0] * n
G = [0] * n
B = [0] * n

r = 0
g = 0
b = 0

for i in range(n):
    if s[i] == "R":
        r += 1
        R[i] = r
    elif s[i] == "G":
        g += 1
        G[i] = g
    else:
        b += 1
        B[i] = b

for i in range(n-2):
    for j in range(i+1,n-1):
        x = s[i]
        y = s[j]
        
        if x != y:
            if "R" not in [x,y]:
                ans += R[n-1] - R[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "R":
                        ans -= 1
                    
            if "G" not in [x,y]:
                ans += G[n-1] - G[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "G":
                        ans -= 1
                    
            if "B" not in [x,y]:
                ans += B[n-1] - B[j]
                
                if 2*j-i < n:
                    if s[2*j-i] == "B":
                        ans -= 1
    
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
  
ans = 0
for i1 in range(10):
  for i2 in range(10):
    for i3 in range(10):
      n1 = 0
      n2 = 0
      n3 = 0
      p1 = 0
      p2 = 0
      p3 = 0
      while(p1 < len(S)):
        if(int(S[p1]) == i1):
          p2 = p1 + 1
          n1 = 1
          break
        p1 += 1
      while(p2 < len(S)):
        if(int(S[p2]) == i2):
          p3 = p2 + 1
          n2 = 1
          break
        p2 += 1
      while(p3 < len(S)):
        if(int(S[p3]) == i3):
          n3 = 1
          break
        p3 += 1
      if(n1 == 1 and n2 == 1 and n3 == 1):
        ans += 1
        
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
  
ans = 0
for i1 in range(10):
  for i2 in range(10):
    for i3 in range(10):
      p = 1
      for f in range(N):
        if(p == 1 and S[f] == str(i1)):
          p = 2
        elif(p == 2 and S[f] == str(i2)):
          p = 3
        elif(p == 3 and S[f] == str(i3)):
          ans += 1
          break
        
print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())
numalllist = [num for num in range(a, b + 1)]
if 2 * k >= b - a + 1 :
    for i in numalllist :
        print(i)
else :
    for i in numalllist[:k] :
        print(i)
    for i in numalllist[-k:] :
        print(i)


### FIXED CODE ###

a, b, k = map(int, input().split())
if 2 * k >= b - a + 1 : 
    i = a
    while i <= b :
        print(i)
        i += 1
else :
    i = a
    while i <= a + k - 1 :
        print(i)
        i += 1
    i = b - k + 1
    while i <= b :
        print(i)
        i += 1
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    dic = [[] for _ in range(C + 1)]
    for _ in range(N):
        s, t, c = input().split()
        dic[int(c)].append([int(s), int(t)])
    for c in range(C + 1):
        l = len(dic[c])
        if l == 1:
            continue
        dic[c] = sorted(dic[c])
        i = 0
        while i < l - 1:
            if i < l - 1 and dic[c][i][1] == dic[c][i + 1][0]:
                dic[c][i + 1][0] = dic[c][i][0]
                dic[c].pop(i)
                l -= 1
            else:
                i += 1
    f = [0 for _ in range(100002)]
    for c in range(C + 1):
        for t in dic[c]:
            f[t[0]] += 1
            f[t[1] + 1] -= 1

    ans = 0
    for i in range(1, 100001):
        f[i] += f[i - 1]
        if ans < f[i]:
            ans = f[i]
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    dic = [[] for _ in range(C + 1)]
    for _ in range(N):
        s, t, c = input().split()
        dic[int(c)].append([int(s), int(t)])
    for c in range(C + 1):
        l = len(dic[c])
        if l == 1:
            continue
        dic[c] = sorted(dic[c])
        i = 0
        while i < l - 1:
            if i < l - 1 and dic[c][i][1] == dic[c][i + 1][0]:
                dic[c][i + 1][0] += 1
            else:
                i += 1
    f = [0 for _ in range(100002)]
    for c in range(C + 1):
        for t in dic[c]:
            f[t[0]] += 1
            f[t[1] + 1] -= 1
    ans = 0
    for i in range(1, 100001):
        f[i] += f[i - 1]
        if ans < f[i]:
            ans = f[i]
    print(ans)

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

n,k = map(int,input().split())
p_list = list(map(int,input().split()))
result_list = []
for i in range(n-k+1):
  p_part = p_list[i:i+k]
  result = 0
  for p in p_part:
    result += (p + 1)/2
  result_list.append(result)
print(max(result_list))
  

### FIXED CODE ###

n,k = map(int,input().split())
p_list = list(map(int,input().split()))
ruiseki = []
a = 0
for i in range(n):
  a += p_list[i]
  ruiseki.append(a)
res = -1
val_list = []
for m in range(n-k):
  val = ruiseki[k+m] - ruiseki[m]
  val_list.append(val)
if n ==k :
  	print((sum(p_list) + k)/2)
else:
	print((max(val_list)+k)/ 2)
### BUGGY CODE ###

s = input()
q = int(input())

def addflont(s,c):
    return c+s
def addback(s,c):
    return s+c

reverse = 0

for i in range(q):
    t = list(map(str,input().split()))
    if t[0]=="1":
        reverse += 1
    if t[0]=="2":
        if t[1]=="1":
            if reverse%2==0:
                s = addflont(s,t[2])
            else:
                s = addback(s,t[2])
        elif t[1]=="2":
            if reverse%2==0:
                s = addback(s,t[2])
            else:
                s = addflont(s,t[2])

if reverse%2==1:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###



s = input()
q = int(input())

def addflont(s,c):
    text = "".join([c,s])
    return text
def addback(s,c):
    text = "".join([s,c])
    return text

reverse = 0
r = "";u = ""
for i in range(q):
    t = input()
    if t[0]=="1":
        reverse = reverse^1
    if t[0]=="2":
        if t[2]=="1":
            if reverse==0:
                r = addflont(r,t[4])
            else:
                u = addback(u,t[4])
        elif t[2]=="2":
            if reverse==0:
                u = addback(u,t[4])
            else:
                r = addflont(r,t[4])

s = r + s + u
if reverse==1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline

h, n = map(int, input().split())
a = map(int, read().split())
ab = zip(a, a)

dp = [10 ** 18] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
### BUGGY CODE ###

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


k = 1
s = 0
count = 0

if k in a:
    s = a.index(k)
    a = a[s:]
    k += 1

if k in a:
    s = a.index(k)
    a = a[s:]
    k += 1


for i in range(len(a)):
    if k in a:
        s = a.index(k)
        a = a[s:]
        k += 1
        count += 1
    else:
        break

if 1 in m:
    print(n-(k-1))
else:
    print(-1)
 

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
j=1
for i in range(N):
    if j==A[i]:
        j+=1
 
if j==1:
  print(-1)
else:
  print(N-j+1)
### BUGGY CODE ###

# http://www.nct9.ne.jp/m_hiroi/puzzle/prime.html
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff

# http://www.nct9.ne.jp/m_hiroi/puzzle/divisor.html#ans03
def divisor_num(n):
    a = 1
    for _, x in factorization(n):
        a *= x + 1
    return a

N = int(input())
ans = 0
for i in range(1, N):
    ans += divisor_num(N-i)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
a = 1
while(a < N):
    ans += (N-1)//a # bmax
    a += 1

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

import sys
from numba import njit
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

@njit
def check(t, As):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            #index = bisect_right(As, t//A, lo = i+1) - (i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] <= t//A:
                    l = mid
                else:
                    r = mid
            index = r - (i+1)
        elif A < 0:
            #index = N - bisect_left(As, -((-t)//A), lo = i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] < -((-t)//A):
                    l = mid
                else:
                    r = mid
            index = N - r
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        

l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    if check(mid, As):
        l = mid
    else:
        r = mid

print(r)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

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

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
flag[0] = 1
while q:
    temp = q.pop(0)
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)

### FIXED CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
while q:
    temp = q.pop()
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)