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

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

A.insert(0,-1)
root = [1]
next = A[1]
rf = 0

for _ in range(K):
    if next in root:
        rf = root.index(next)
        root = root[rf:]
        break
    root.append(next)
    next = A[next]

print(root[(K - rf) % len(root)])


### FIXED CODE ###

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

A.insert(0,-1)
root = [1]

for _ in range(N-1):
    root.append(A[root[-1]])

if K > N:
    start = root.index(root[-1])
    index = (K - start) % (len(root) - start - 1) + start
    ans = root[index]
else:
    ans = root[K]

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

from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
mwi=deque([])
s = [list(map(int, input().split())) for i in range(m)]
lis = [deque([]) for i in range(h)]

for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  lis[a].append(b)
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)

for i in mwi:
  for j in mhi:
    if not i in lis[j]:
      print(mh+mw)
      quit()
      
print(mh+mw-1)

### FIXED CODE ###

from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
dic = {}
mwi=deque([])
#ans =[[0]*w for i in range(h)]
s = [list(map(int, input().split())) for i in range(m)]
 
for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  if not a in dic:
    dic[a] = {}
    dic[a][b]=1
  else:
    dic[a][b]=1
 
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)
 
  #ans[a][b]+=1

for i in mhi:
  for j in mwi:
    if not j in dic[i]:
      print(mw+mh)
      quit()

print(mh+mw-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())

def solve(N, W): 
    dp = [0]*(W+1)
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp_next = [0] * (W+1)
        for w in range(1, W+1):
            if w >= wi:
                dp_next[w] = max(dp[w - wi] + vi, dp[w])
            else:
                dp_next[w] = dp[w]
        dp = dp_next
    return dp[-1]

print(solve(N, W))

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype='int64')

def solve(N, W):
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp[i][:wi] = dp[i-1][:wi]
        dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)
    return dp[N-1][W]

print(solve(N, W))
### BUGGY CODE ###

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
back2 = 0
back1 = 1
MOD = int(1e9+7)

for i in range(n):
    if i + 1 in bad:
        back2, back1 = back1%MOD, 0
    else:
        back2, back1 = back1%MOD, (back2+back1)%MOD

print(back1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(150000)

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))
### BUGGY CODE ###

# Acceptance of input

import sys

f_i = sys.stdin

n = int(f_i.readline())

edges = [[None] * n for i in range(n)]

for l_i in f_i:
    s, t, w = map(int, l_i.split())
    edges[s][t] = w
    edges[t][s] = w

# dfs tree walk 1

import collections

path = collections.deque()
path.append(0)

distance = 0
max_distance = 0

end_point = 0

unvisited = [False] + [True] * (n - 1)

while True:
    u = path[-1]
    adj_e = edges[u]
    for v, e in enumerate(adj_e):
        if unvisited[v] and e != None:
            path.append(v)
            distance += e
            unvisited[v] = False
            if max_distance < distance:
                max_distance = distance
                end_point = v
            break
    if u == path[-1]:
        path.pop()
        if path:
            distance -= edges[u][path[-1]]
        else:
            break

# Measurement of diameter(dfs tree walk 2)

path.append(end_point)

distance = 0
diameter = 0

unvisited = [True] * n
unvisited[end_point] = False

while True:
    u = path[-1]
    adj_e = edges[u]
    for v, e in enumerate(adj_e):
        if unvisited[v] and e != None:
            path.append(v)
            distance += e
            unvisited[v] = False
            if diameter < distance:
                diameter = distance
                end_point = v
            break
    if u == path[-1]:
        path.pop()
        if path:
            distance -= edges[u][path[-1]]
        else:
            break

# output

print(diameter)

### FIXED CODE ###

# Acceptance of input

import sys

f_i = sys.stdin

n = int(f_i.readline())

edges = [[] for i in range(n)]

for l_i in f_i:
    s, t, w = map(int, l_i.split())
    edges[s].append((t, w))
    edges[t].append((s, w))

# Tree Walk function

import collections

def tree_walk(start, switch = 0):
    path = collections.deque()
    path.append(start)

    weight = collections.deque()
    weight.append(0)
    
    unvisited = [True] * n
    unvisited[start] = False
    
    rest = n - 1
    end_point = start
    diameter = 0
    
    while True:
        u = path[-1]
        for v, w in edges[u]:
            if unvisited[v]:
                path.append(v)
                unvisited[v] = False
                rest -= 1
                weight.append(w)
                break

        if u == path[-1]:
            distance = sum(weight)
            if diameter < distance:
                diameter = distance
                end_point = u
            if rest == 0:
                break
            path.pop()
            weight.pop()

    if switch:
        print(diameter)
    else:
        return end_point

# Output

tree_walk(tree_walk(0), 1)
### BUGGY CODE ###

from collections import deque

n = int(input())

nodes = [set() for i in range(n+1)]
dis = [dict() for i in range(n+1)]
ans = [-1 for i in range(n+1)]

for _ in range(n-1):
    a,b,c = map(int,input().split())
    nodes[a].add(b)
    nodes[b].add(a)
    dis[a][b] = c
    dis[b][a] = c

#print(nodes)
#print(dis)

Q,K = map(int,input().split())

q = [K]
d = 0
ans[K] = 0
c = 0
while True:
    now = q[-1]
    nex = -1
    for x in nodes[now]:
        if ans[x] == -1:
            nex = x
            break
    if nex == -1:
        if c >= n-1:
            break
        else:
            q.pop()
            d -= dis[now][q[-1]]

    else:
        nodes[now].remove(nex)
        nodes[nex].remove(now)
        d += dis[now][nex]
        q.append(nex)
        ans[nex] = d
        c += 1

#print(ans)

for _ in range(Q):
    x,y = map(int,input().split())
    print(ans[x] + ans[y])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())

vertex = [{} for _ in range(N)]

for i in range(N-1):
    a,b,c = map(int,input().split())
    vertex[a-1][b-1] = c
    vertex[b-1][a-1] = c

Q,K = map(int,input().split())

d = [0 for i in range(N)]

def dfs(v1,v2):
    d[v2] = d[v1] + vertex[v1][v2]
    for v in vertex[v2]:
        if v == v1:
            continue
        dfs(v2,v)

for v in vertex[K-1].keys():
    dfs(K-1,v)

for q in range(Q):
    x,y = map(int,input().split())
    print(d[x-1] + d[y-1])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    A[i] %= (10**9 +7)
for i in range(n-1):
    ans += A[i]*sum(A[i+1:n])
print(ans%(10**9 + 7))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    A[i] %= (10**9 +7)
s = sum(A)
for i in range(n-1):
    s -= A[i]
    ans += A[i]*s
print(ans%(10**9 + 7))
### BUGGY CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    n = int(stdin.readline().rstrip())
    #A, B = map(int, stdin.readline().rstrip().split())
    A = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    ans =1
    for i in range(n):
        ans *= A[i]
    if ans > 10**18:
        print(-1)
    else:
        print(ans)

main()


### FIXED CODE ###

import sys

stdin = sys.stdin

def main():
    n = int(stdin.readline().rstrip())
    A = list(map(int, stdin.readline().rstrip().split()))
    A.sort()
    ans = 1
    for i in range(n):
        if ans > 10**18:
            if A[0] == 0:
                print(0)
                exit()
            print(-1)
            exit()
        ans *= A[-i]
    print(ans if ans <= 10**18 else -1)


main()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ab = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

edge = [[0]*N for _ in range(N)]
for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

K = 0
for i in graph:
	K = max(K, len(graph[i]))

def DFS(i, color_from):  # color_fromからきた色を使わない
	can_use_color = list(range(1, K+1))
	for node in graph[i]:
		if not edge[i][node]:
			use_color = can_use_color.pop()
			if use_color == color_from:
				use_color = can_use_color.pop()
			edge[i][node] = use_color
			edge[node][i] = use_color
			DFS(node, use_color)

DFS(0, None)

print(K)
for a, b in ab:
	print(edge[a-1][b-1])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

	# edge = [[0]*N for _ in range(N)]
	edge = defaultdict(int)
	for a, b in ab:
		graph[a-1].append(b-1)
		graph[b-1].append(a-1)

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	q = deque()
	q.append((0, None))

	while q:
		i, color_from = q.popleft()
		tmp = -1
		for node in graph[i]:
			str_ = "{},{}".format(i, node)
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge["{},{}".format(node, i)] = use_color
				q.append((node, use_color))
	print(K)
	for a, b in ab:
		print(edge["{},{}".format(a-1, b-1)])


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

s = input()
num = len(s)

x = 0
for i in range(4,num+1):
    for j in range(num - i + 1):
        if int(s[j:j+i]) % 2019 == 0:
            x += 1

print(x)


### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

import sys
sys.setrecursionlimit(10000000) 

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    mems = [False] * (N+1)

    def rec(target):
        if target in As:
            return 0
        
        if target == 1:
            return 1
        
        if target == 2:
            return 2 if 1 not in As else 1

        if not mems[target]:
            one = rec(target-1)
            two = rec(target-2)
            mems[target] = one + two
        
        return mems[target]
    
    print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    As.sort()

    cnts = [False] * (N+1)
    ptr = 0
    for i in range(N+1):
        c = 0
        if ptr < len(As) and i == As[ptr]:
            c = 0
            ptr = ptr + 1
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = (cnts[i-2] + cnts[i-1])%1000000007
        cnts[i] = c

    print(cnts[N])

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

#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

Number = []
Total = 0

Number = [A.count(i+1) for i in range(N)]
Total = sum([Number[i]*(Number[i]-1)/2 for i in range(N)])

for Ak in A:
    print(int(Total - Number[Ak-1]+1))

    

### FIXED CODE ###


import collections

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

C = collections.Counter(A)

Total = sum([i*(i-1)/2 for i in C.values()])

for Ak in A:
    print(int(Total - C[Ak]+1))
### BUGGY CODE ###

import bisect
n,k=map(int,input().split())
A=[]
for i in range(n):
  A.append(int(input())-k)
AA=[0]*(n+1)
AA[-2]=A[-1]
for i in reversed(range(n-1)):
  AA[i]=AA[i+1]+A[i]
ans=0
B=[]
for i in range(n):
  B.append(AA[i])
  B.sort()
  ans+=(i+1)-bisect.bisect_left(B,AA[i+1])
print(ans)




### FIXED CODE ###

n,k=map(int,input().split())
A=[]
for i in range(n):
  A.append(int(input())-k)
AA,BB=[0]*(n+1),[0]*(n+1)
AA[-2]=A[-1]
BB[-2]=A[-1]
for i in reversed(range(n-1)):
  AA[i]=AA[i+1]+A[i]
  BB[i]=BB[i+1]+A[i]
BB.sort()
cur=1
D=dict()
D[BB[0]]=cur
for i in range(1,n+1):
  if BB[i]==BB[i-1]:
    continue
  else:
    cur+=1
    D[BB[i]]=cur
AAA=[0]*(n+1)
for i in range(n+1):
  AAA[i]=D[AA[i]]

nn=18
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

ans=0
for i in range(n+1):
  ans+=i-bitsum(BIT,AAA[i]-1)
  bitadd(BIT,AAA[i],1)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
summ = 0

# 組み合わせの数
# a, b, cが同じは1pattern
# a, b, cのうち、２つが同じパターンは３
# a, b, cのうち、全て異なるパターンは6
# つまり、３つの数の組み合わせの数を求め、各パターン倍すればよい

# タプルで集合を作成する
st = set()
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sort_abc = sorted([a, b, c])
            st.add(tuple(sort_abc))
# print(st)
for s in st:
    if s[0] == s[1] == s[2]:
        summ += reduce(math.gcd, s)
        # print(0, s)
    elif s[0] == s[1] or s[0] == s[2] or s[1] == s[2]:
        summ += 3*reduce(math.gcd, s)
        # print(1, s)
    else:
        summ += 6*reduce(math.gcd, s)
        # print(2, s)
print(summ)

### FIXED CODE ###

import math
k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        num = math.gcd(i, j)
        for l in range(1, k+1):
            ans += math.gcd(num, l)

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

def main(): 
    n,k = map(int,input().split())
    LR = [list(map(int,input().split())) for _ in range(k)]

    dp = [0]*(n*2 + 100)
    dp[1] = 1
    dp[2] = -1
    for i in range(1,n + 1):
        dp[i] += dp[i - 1]
        for l,r in LR:
            if i + l > n:
                continue
            dp[l + i] += dp[i]
            dp[r + i + 1] -= dp[i]        
    print(dp[n]%998244353) 
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main(): 
    mod = 998244353
    n,k = map(int,input().split())
    LR = [list(map(int,input().split())) for _ in range(k)]

    dp = [0]*(n*2 + 100)
    dp[1] = 1
    dp[2] = -1
    for i in range(1,n + 1):
        dp[i] = (dp[i] + dp[i - 1])%mod
        for l,r in LR:
            if i + l > n:
                continue
            dp[l + i] = (dp[l+i] + dp[i])%mod
            dp[r + i + 1] = dp[r+i+1] - dp[i]  if dp[r+i+1] - dp[i] > 0 else dp[r+i+1] - dp[i] + 998244353
    print(dp[n]%998244353) 
    return

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

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

s = 1

for i in a:
    s = s*i
if s > pow(10, 18):
    print(-1)
else:
    print(s)


### FIXED CODE ###

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

s = 1
mod = pow(10, 18)

if 0 in a:
    print(0)
    exit()

for i in a:
    s = s*i
    if s > mod:
        print(-1)
        exit()
else:
    print(s)
### BUGGY CODE ###

r,g,b,n = [int(x) for x in input().split()]

ans = 0

for x in range(n//r + 1):
    for y in range(n // g + 1):
        if (n - (r * x + g * y)) % b == 0 and (n - (r*x + g*y)) >= 0:
            ans += 1
print(ans)

### FIXED CODE ###

r,g,b,n = [int(x) for x in input().split()]

ans = 0

for x in range(n//r + 1):
    for y in range(n // g + 1):
        if (n - (r * x + g * y)) % b == 0 and (n - (r*x + g*y)) >= 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
def main():
    def add(i, x):
        while i <= size:
            tree[i] += x
            i += i & -i
    def sum(i):
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    size = n + 2
    tree = [0] * (size + 1)
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

### FIXED CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()
### BUGGY CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = 10**9+7

ans = 0
for i in range(n-1):
    for j in range(m-1):
        s = (x[i+1] - x[i])*(y[j+1] - y[j])
        ans = (ans + s * (((i+1) * (n-i-1))%mod) * (((j+1) * (m-j-1))%mod)) % mod

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = 10**9+7

ans = 0
y01 = (y[1] - y[0])%mod
ynum = m-1
for i in range(n-1):
    s = (((x[i+1] - x[i])%mod) * y01) % mod
    xnum = (i+1) * (n-i-1)
    ans = (ans + (s*xnum*ynum) % mod) % mod
band = ans

inv = [0] * (m + 1)
inv[1] = 1
for i in range(2, m):
    inv[i] = mod - inv[mod % i] * (mod // i) % mod

for j in range(1, m-1):
    band = (((((band * inv[j])%mod) * inv[m-j])%mod) * (((j+1) * (m-j-1))%mod))%mod
    band = ((band * ((y[j+1] - y[j])%mod))%mod * pow(((y[j]-y[j-1])%mod), mod-2, mod))%mod
    ans = (ans + band)%mod

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

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

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

price_list = []
stock_list = []
for i in range(N):
    A, B = map(int, input().split())
    index = bisect.bisect_left(price_list, A)
    price_list.insert(index, A)
    stock_list.insert(index, B)

ans = 0
rest = M
for i in range(N):
    if stock_list[i] < rest:
        ans += price_list[i] * stock_list[i]
        rest -= stock_list[i]
    else:
        ans += rest * price_list[i]
        break

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter


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

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


def main():
    b = sorted(a, key=itemgetter(0))
    m = 0
    cost = 0
    for i in range(N):
        if (m + b[i][1]) <= M:
            m += b[i][1]
            cost += (b[i][0] * b[i][1])
        else:
            cost += (b[i][0] * (M-m))
            return cost
    return cost


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

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# 美味しさ P 以上の組が K 個以上あるか
def is_exist_K_tuples(P):
    cnt = 0
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                if A[i] + B[j] + C[k] >= P:
                    cnt += 1
                if cnt >= K:
                    return True
    return False

# 二部探索で K 個以上の組がギリギリ存在する美味しさのラインをサーチ
left = 0
right = A[0] + B[0] + C[0]
while left <= right:
    border = (left + right) // 2
    if is_exist_K_tuples(border):
        left = border + 1
    else:
        right = border - 1
else:
    # 最後の border で K 個あるかは保証されていないので再チェックしてダメなら補正
    if not is_exist_K_tuples(border):
        border -= 1

# 枝刈り全探索で border + 1 以上の美味しさを列挙
result = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if A[i] + B[j] + C[k] >= border + 1:
                result.append(A[i] + B[j] + C[k])
            else:
                break

# 残りがあればそれはすべて border のはず
remains = K - len(result)
for _ in range(remains):
    result.append(border)

result.sort(reverse=True)
for r in result:
    print(r)

### FIXED CODE ###

from itertools import product

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for a, b in product(A, B)]
AB.sort(reverse=True)

ABC = [ab + c for ab, c in product(AB[:K], C)]
ABC.sort(reverse=True)

for abc in ABC[:K]:
    print(abc)