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

#!/usr/bin/env python3
import os


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n = inp[0]
    m = inp[1]

    wi = inp[2]
    vi = inp[3]

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-1])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-(i+1)] != '?':
			num = int(s[-(i+1)])
			for j in range(13):
				dp[i][(a*num+j)%13] += dp[i-1][j] % MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k] % MOD
				#a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

import sys

N, Q = map(int, input().split())
S = input()
P = [[int(v) - 1 for v in sys.stdin.readline().split()] for _ in range(Q)]
X = [0] * (N - 1)

for i in range(N - 1):
    if S[i:i + 2] == 'AC':
        X[i] = 1

for l, r in P:
    cnt = sum(X[l:r])
    print(cnt)


### FIXED CODE ###

import sys

N, Q = map(int, input().split())
S = input()
P = [[int(v) - 1 for v in sys.stdin.readline().split()] for _ in range(Q)]
X = [0] * (N + 1)

for i in range(N):
    if S[i:i + 2] == 'AC':
        X[i + 1] = X[i] + 1
    else:
        X[i + 1] = X[i] 


for l, r in P:
    print(X[r] - X[l])
### BUGGY CODE ###

def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N, K = mapint_inp()

l = list(range(N+1))
mn_list = []
for i in range(K, N+2):
    mn_list.append(sum(l[:i]))

r = l[::-1]
mx_list = []
for i in range(K, N+2):
    mx_list.append(sum(r[:i]))

ans = 0
for j in range(len(mn_list)):
    ans += mx_list[j]-mn_list[j]+1

print(ans)

### FIXED CODE ###

def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

N, K = mapint_inp()
MOD = 10**9+7

ans = 0
for i in range(K, N+2):
    mn = i*(i-1) // 2
    mx = i*(2*N-i+1) // 2
    ans += mx - mn + 1

print(ans%MOD)
### BUGGY CODE ###

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

dp=[0]*(N)

for i in range(1,N+1):
    if i==1 and 1 not in a:
        dp[0]=1
    elif i==2:
        if 2 in a:
            dp[1]=0
        else:
            dp[1]+=dp[0]+1

    elif i not in a:
        dp[i-1]=dp[i-2]+dp[i-3]

print(dp[N-1]%1000000007)
    

### FIXED CODE ###

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

a.append(N+10)
dp=[0]*(N)
j=0

for i in range(1,N+1):
    if i==1 and 1!=a[j]:
        dp[0]=1
    elif i==2:
        if 2==a[j]:
            dp[1]=0
            j+=1
        else:
            dp[1]=dp[0]+1

    elif i!=a[j]:
        dp[i-1]=dp[i-2]+dp[i-3]
    else:
        j+=1
    

print(dp[N-1]%1000000007)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[False]*n
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if not(a[i]):
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if not(a[x]):
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")

### FIXED CODE ###

n,m=map(int,input().split())
a=[None]*n
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if a[i]==None:
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if a[x]==None:
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")
### BUGGY CODE ###

n,k = map(int,input().split())
c = [int(input()) for _ in range(n)]

c.sort()

ans = []
for i in range(n-k+1):
    ans.append(max(c[i:k+i])-min(c[i:k+i]))

print(min(ans))

### FIXED CODE ###

n,k = map(int,input().split())
c = [int(input()) for _ in range(n)]
c.sort()
ans = []
for i in range(n-k+1):
    ans.append(c[i+k-1]-c[i])
print(min(ans))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc137/tasks/abc137_c
# C - Green Bin
import collections
import itertools

n = int(input().split()[0])
s_list = []
c_list = []

for _ in range(n):
    s = input().split()[0]
    s_list.append(s)
    c_list.append(collections.Counter(s))

p = itertools.combinations(c_list, 2)
ans = sum([1 if a == b else 0 for a, b in list(p)])
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc137/tasks/abc137_c
# C - Green Bin
import collections
import itertools
import math

n = int(input().split()[0])
s_list = []
c_list = []

for _ in range(n):
    s = input().split()[0]
    s_list.append(''.join(sorted(s)))

counter = collections.Counter(s_list)

def C(n, k):
    return math.factorial(n) / (math.factorial(k) * math.factorial(n-k))

p_list = [C(value, 2) for key, value in counter.items() if value > 1]
ans = int(sum(p_list))

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

limit, sum_xyz = map(int, input().split())

pair = list()
x_bottom = sum_xyz - 2*limit
x_bottom = 0 if x_bottom < 0 else x_bottom

for i in range(limit, x_bottom - 1, -1):
    x = i
    y_limit = 0
    if sum_xyz - x >= limit:
        y_limit = limit
    else:
        y_limit = sum_xyz - x
    y_bottom = sum_xyz - x - limit
    y_bottom = 0 if y_bottom < 0 else y_bottom

    for j in range(y_limit, y_bottom - 1, -1):
        y = j
        z = sum_xyz - x - y
        pair.append([x, y, z])
ans = len(pair)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    K,S = [int(x) for x in input().split()]
 
    count = 0
 
    for x in range(K+1):
        for y in range(K+1):
            z = S - (x + y)
            if z >= 0 and z <= K:
                count += 1
 
    print(count)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            temp = A[i]
            left = i - temp
            right = i + temp + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B

    print(*A)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

S = input()
n = len(S)
DP = [0]

for s in S:
    D = [-float('inf')] * (len(DP) + 1)
    for i in range(len(DP)):
        if s == 'g':
            if i == 0:
                D[i + 1] = max(D[i + 1], DP[i])
            else:
                D[i + 1] = max(D[i + 1], DP[i])
                D[i - 1] = max(D[i - 1], DP[i] + 1)
        if s == 'p':
            if i == 0:
                D[i + 1] = max(D[i + 1], DP[i] - 1)
            else:
                D[i + 1] = max(D[i + 1], DP[i] - 1)
                D[i - 1] = max(D[i - 1], DP[i])
    DP = D
print(max(DP))

### FIXED CODE ###

S = input()
N = len(S)

print(N // 2 - S.count('p'))
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            ans=max(ans,c+1)
            q.append((ny,nx,c+1))

  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

def W(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w,l= map(int,input().split()) #n:頂点数　w:辺の数

d = [[10**14]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    if z>l:
      continue
    x=x-1
    y=y-1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
D=W(d)
G=[[10**4]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if D[i][j]>l:
      continue
    G[i][j]=1
WW=W(G)
for i in range(int(input())):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  if WW[a][b]>=10**4:
    print(-1)
  else:
    print(WW[a][b]-1)

### FIXED CODE ###

def W(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w,l= map(int,input().split()) #n:頂点数　w:辺の数

d = [[10**14]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    if z>l:
      continue
    x=x-1
    y=y-1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
D=W(d)
G=[[10**4]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if D[i][j]>l:
      continue
    G[i][j]=1
WW=W(G)
for i in range(int(input())):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  if WW[a][b]>=10**4:
    print(-1)
  else:
    print(WW[a][b]-1)
### BUGGY CODE ###

import bisect

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

L.sort()
cnt = 0

for i in range(N):
    for j in range(i + 1, N):
        idx = bisect.bisect_left(L, L[i] + L[j], lo=j + 1)
        cnt += max(0, idx - (j + 1))
        
print(cnt)

### FIXED CODE ###

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


L.sort(reverse=True)
dic = {}
cnt = 0

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

        if s not in dic:
            dic[s] = 1
        else:
            dic[s] += 1

for i in range(N - 2):
    p = L[i]

    if i > 0:
        for x in range(i + 1, N):
            dic[p + L[x]] -= 1

    for key, value in dic.items():
        if key > p:
            cnt += value

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

# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


n, k = inpl()
H = inpl()

if k >= n: k = n - 1
H = [H[0]] + H
dp = [INF] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if i - j < 0: break
        dp[i] = min(dp[i], abs(H[i] - H[i - j]) + dp[i - j])
    # print(dp)

print(dp[n])


### FIXED CODE ###

# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


n, k = inpl()
H = inpl()

if k >= n: k = n - 1
H = [H[0]] + H
dp = [INF] * (n + 1)
dp[0] = 0

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if i - j < 0: break
        dp[i] = min(dp[i], abs(H[i] - H[i - j]) + dp[i - j])
    # print(dp)

print(dp[n])
### BUGGY CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))
q = int(input())
num_li=[list(map(int,input().split())) for i in range(q)]


c = collections.Counter(li)

for i,j in num_li:
    s = 0
    if i in c:
        cnt = c.pop(i)
        c[j] += cnt
    for k, v in c.items():
        s += k * v
    print(s)

### FIXED CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))
q = int(input())
num_li=[list(map(int,input().split())) for i in range(q)]

c = collections.Counter(li)

li_sum = sum(li)

for i,j in num_li:
    s = 0
    if i in c:
        cnt = c.pop(i)
        c[j] += cnt
        li_sum = li_sum - (i*cnt) + (j*cnt)
    print(li_sum)
### BUGGY CODE ###

import itertools as it


def is_753(n):
    dic753 = {}
    for i in str(n):
        if i == "7":
            dic753[7] = True
        elif i == "5":
            dic753[5] = True
        elif i == "3":
            dic753[3] = True
        else:
            return False
    if len(dic753) >= 3:
        return True
    else:
        return False


N = int(input())
dig = 3
candidate = []
dig = 3
while True:
    for i in it.product([3, 5, 7], repeat=dig):
        a = int("".join(map(str, i)))
        if a > N:
            break
        else:
            candidate.append(a)
    dig += 1
for i in candidate:
    if is_753(i):
        ans += 1
print(ans)


### FIXED CODE ###

import itertools as it

N = input()
list_753 = []
for i in range(3, len(N) + 1):
    for i_753 in it.product("357", repeat=i):
        if "3" in i_753 and "5" in i_753 and "7" in i_753:
            list_753.append(int("".join(i_753)))

ans = 0
for i in list_753:
    if i <= int(N):
        ans += 1
    else:
        break
print(ans)
### BUGGY CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

    if P == 2:
        cnt = N * (N + 1) // 2
        for i, si in enumerate(S):
            if si & 1:
                cnt -= i + 1
        print(cnt)
        return

    cnt = 0
    for i in range(N):
        ans = 0
        for j in range(i, N):
            sj = S[j]
            ans = 10*ans + sj
            #print(ans, ans % P)
            if ans % P == 0:
                cnt += 1
    print(cnt)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

    if P == 2 or P == 5:
        cnt = 0
        for i, si in enumerate(S):
            if si % P == 0:
                cnt += i + 1
        print(cnt)
        return

    T = [0] * P
    T[0] = 1

    ss, p10 = 0, 1
    for s1 in S[::-1]:
        ss += p10 * s1
        ss %= P
        T[ss] += 1
        p10 = 10 * p10 % P

    ans = 0
    for i in T:
        ans += i*(i-1)//2
    print(ans)

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

S = input()
Q = int(input())

st = True
for _ in range(Q):
    Query = input().split()
    if Query[0] == '1':
        st = not st
    else:
        if (Query[1] == '1') ^ st:
            S += Query[2]
        else:
            S = Query[2] + S
if st:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())

st = True
deq = deque(S)
for _ in range(Q):
    Query = input().split()
    if Query[0] == '1':
        st = not st
    else:
        if (Query[1] == '1') ^ st:
            deq.append(Query[2])
        else:
            deq.appendleft(Query[2])
if st:
    print(''.join(deq))
else:
    print(''.join(reversed(deq)))
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
q=[]
#from collections import Counter
#q=Counter(d)

for i in range(max(d)+1):
    q.append(d.count(i))

if q[0]!=1 or d[0]!=0:
    print(0)
    exit()

ans=1
for i in range(1,max(d)+1):
    ans*=q[i-1]**q[i]
    if ans == 0:
        break
print(ans%998244353)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
 
from collections import Counter
q=Counter(d)

# 例外対応
if q[0]!=1 or d[0]!=0:
  print(0)
  exit()

ans = 1
for i in range(1,max(d)+1):
  ans *= q[i-1]**q[i]
  if ans == 0:
    break
print(ans%998244353)
### BUGGY CODE ###

K, S = [int(a) for a in input().split()]

cnt = 0
for x in range(0,K+1):
  if x > S:
    continue
  for y in range(0,K+1):
    if x+y > S:
      continue
    for z in range(0,K+1):
      check = x+y+z
      if check == S:
        cnt += 1
      elif check > S:
        continue
        
print(cnt)

### FIXED CODE ###

K, S = [int(a) for a in input().split()]

cnt = 0
for x in range(0,K+1):
  if x > S:
    continue
  for y in range(0,K+1):
    if x+y > S:
      continue
    elif x+y+K < S:
      continue
    else:
      cnt +=1
        
print(cnt)
### BUGGY CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A[A > 0]  # target以下の値がA[i]の相方
    n_comb += sum(np.searchsorted(A, target, side="right"))

    # A[i] == 0であるA[i]について
    n_comb += n * len(A[A == 0]) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A[A < 0])
    n_comb += sum(n - np.searchsorted(A, target, side="left"))

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= len(A[A * A <= c])
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)

### FIXED CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A=A[:b]+A[b+1:i]
        B=B[:b]+B[b+1:i]
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count) 

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)
### BUGGY CODE ###

import sys
from collections import Counter as ct

def factoring(n):
    root = int(n ** .5) + 1
    arr = []
    for i in range(2, root):
        while(n % i == 0):
            arr.append(i)
            n //= i
    if n > 1:
        arr.append(n)
    return ct(arr)

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

kp = factoring(k)
ap = list(map(factoring, a))
ap0 = ap[0]
for a_cnt in ap[1:]:
    ap0 = ap0 & a_cnt
prod = 1
for p, x in ap0.items():
    prod *= p ** x

ans = 'POSSIBLE' if k % prod == 0 and k <= a[-1] else 'IMPOSSIBLE'
print(ans)


### FIXED CODE ###

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

def lcm(x, y):
    return x if y == 0 else lcm(y, x % y)

l = ar[0]
for a in ar[1:]:
    l = lcm(l, a)

ans = 'POSSIBLE' if k % l == 0 and k <= ar[-1] else 'IMPOSSIBLE'
print(ans)