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

x,y,z,k=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)

sum_ab=[]

for i in a:
    for j in b:
      sum_ab.append(i+j)

sum_ab.sort(reverse=True)
sum_ab=sum_ab[:min(k,x*y)]

sum_abc=[]
for i in sum_ab:
    for j in c:
      sum_abc.append(i+j)

sum_abc.sort(reverse=True)
for v in sum_abc[:k]:
    print(v)

### FIXED CODE ###

x,y,z,k=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)

t=[]

for i in a:
    for j in b:
      t.append(i+j)

t.sort(reverse=True)
t=t[:min(k,x*y)]

ans=[]
for i in c:
    for j in t:
      ans.append(i+j)

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

def xor_operate(a_list):
    result = 0
    for a in a_list:
        result ^= int(a)
    return str(result)



if __name__ == "__main__":
    N = input()
    a_list = input()

    a_list = a_list.split(" ")

    i_list = []
    for i in range(len(a_list)):
        r_list = a_list[:i]+a_list[i+1:]
        i_list.append(xor_operate(r_list))
    print(" ".join(i_list))
    


        



### FIXED CODE ###

def xor_operate(a_list):
    result = 0
    for a in a_list:
        result ^= int(a)
    return result



if __name__ == "__main__":
    N = input()
    a_list = input()

    a_list = a_list.split(" ")

    bit_value = xor_operate(a_list)

    i_list = []
    for a in a_list:
        i_list.append(str(bit_value ^ int(a)))
    print(" ".join(i_list))
### BUGGY CODE ###

N = int(input())

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

lc, uc = {}, {}

for i in b :
    cnt_l, cnt_u = 0, 0
    
    for j in a :
        if j < i :
            cnt_l += 1
            
    lc[i] = cnt_l
    
    for j in c :
        if j > i :
            cnt_u += 1
            
    uc[i] = cnt_u
    
combs = 0
for i in b :
    combs += lc[i] * uc[i]
    
print(combs)
            

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a_s, b_s, c_s = sorted(a), sorted(b), sorted(c)

a_idx, c_idx = 0, 0
small_at, big_at = [], []
small_cnt, big_cnt = 0, 0

for i in b_s :
    while a_idx < N and a_s[a_idx] < i :
        a_idx += 1
        small_cnt += 1
        
    while c_idx < N and c_s[c_idx] <= i :
        c_idx += 1
        big_cnt += 1
        
    small_at.append(small_cnt)
    big_at.append(big_cnt)
    
sum_comb = 0 
for i in range(N) :
    sum_comb += small_at[i] * (N - big_at[i])

print(sum_comb)
### BUGGY CODE ###

N = int(raw_input())
nums = map(int, raw_input().split())
num_t = []
for i,num in enumerate(nums):
    num_t.append([num, i])
num_t = sorted(num_t, key=lambda x: x[0])
for i in range(N):
    num_tmp = num_t
    for j, a in enumerate(num_tmp):
        if a[1] == i:
            num_tmp = num_tmp[0:j] + num_tmp[j+1:N]
    print(num_tmp[(N/2) - 1][0])

### FIXED CODE ###

N = int(raw_input())
nums = map(int, raw_input().split())
num_tmp = []
for a in nums:
    num_tmp.append(a)
nums.sort()
med_1 = nums[N/2 - 1]
med_2 = nums[N/2]
for i in range(N):
    if num_tmp[i] <= med_1:
        print(med_2)
    elif num_tmp[i] >= med_2:
        print(med_1)
### BUGGY CODE ###


#処理内容
def main():
	N = int(input())
	S = []
	for i in range(N):
		s = input()
		S.append(s)
	ans = 0
	for k in range(N):
		judge = "Yes"
		for i in range(N):
			for j in range(N):
				if S[i][(j + k) % N] != S[j][(i + k) % N]:
					judge = "No"
					break
		if judge == "Yes":
			ans += 1
	print(ans * N)

if __name__ == '__main__':
	main()

### FIXED CODE ###

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	S = []
	for i in range(N):
		s = input()
		S.append(s)
	ans = 0
	for k in range(N):
		judge = "Yes"
		for i in range(N):
			for j in range(N):
				if S[i][(j + k) % N] != S[j][(i + k) % N]:
					judge = "No"
					break
		if judge == "Yes":
			ans += 1
	print(ans * N)

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

s = [i for i in input()]
q = int(input())
for _ in range(q):
    s_ = input()
    if len(s_) == 1:
        s = s[::-1]
    else:
        _, f, c = map(str, s_.split())
        if f == "1": s.insert(0, c)
        else: s.append(c)
print("".join(s))

### FIXED CODE ###

from collections import deque
s = deque([i for i in input()])
q = int(input())
cnt = 0
for _ in range(q):
    s_ = input()
    if len(s_) == 1: cnt += 1
    else:
        if (int(s_[2]) + cnt % 2) % 2 == 0: s.append(s_[4])
        else: s.appendleft(s_[4])
if cnt % 2 == 1: print("".join(list(s)[::-1]))
else: print("".join(s))
### BUGGY CODE ###

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

yn=""
na=y//10000
nb=y//5000
for a in range(na+1):
    for b in range(nb+1):
        if y==10000*a+5000*b+1000*(n-a-b) and n>=a+b:
            print(a,b,n-a-b)
            yn="YES"
            break
    if yn=="YES":
        break
if yn!="YES":
    print(-1,-1,-1)
        

### FIXED CODE ###

n,y=map(int,input().split())
    
n10max=y//10000
n5max=y//5000

iskip=0
for n10 in range(n10max,-1,-1):
    if n10*10000>y:
        continue
    for n5 in range(min(n-n10,n5max)+1):
        n1=n-n10-n5
        if n10*10000+n5*5000+n1*1000==y and n1>=0:
            print(n10,n5,n-n10-n5)
            iskip=1
            break
        else:
            continue
    if iskip==1:
        break
    else:
        continue
        
if iskip==0:
    print(-1,-1,-1)
### BUGGY CODE ###

S = input()
S = list(S)
flag = True
res = 0
while flag:
    flag = False
    for i in range(len(S) - 1):
        if S[i] == 'B' and S[i+1] == 'W':
            S[i] = 'W'
            S[i+1] = 'B'
            res += 1
            flag = True
print(res)

### FIXED CODE ###

S = input()
res = 0
count = 0
for i in range(len(S)):
    if S[i] == 'B':
        count += 1
    if S[i] == 'W':
        res += count
       
print(res)
### BUGGY CODE ###

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

import sys

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

    nw = 1
    lp0 = [1]
    for i in range(N):
        nw = A[nw-1]
        if nw in lp0:
            break
        else:
            lp0.append(nw)
    lpc = i+1 - lp0.index(nw)
    lp = lp0[-lpc:]

    if K<=len(lp0)-1:
        print(lp0[K])
    else:
        K-= len(lp0)-1
        K=K%lpc - 1
        print(lp[K])

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import sys

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

    nw = 1
    lp0 = [1]
    lpl = {1}
    for i in range(N):
        nw = A[nw-1]
        if nw in lpl:
            break
        else:
            lp0.append(nw)
            lpl.add(nw)
    lpc = i+1 - lp0.index(nw)
    lp = lp0[-lpc:]

    if K<=len(lp0)-1:
        print(lp0[K])
    else:
        K-= len(lp0)-1
        K=K%lpc - 1
        print(lp[K])

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

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0]*C for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp = [[[0]*4 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+I[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])


# print(*dp, sep=' \n')

ans = 0
for k in range(4):
    ans = max(ans, dp[R-1][C-1][k])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0]*C for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp0 = [[0 for j in range(C+1)] for i in range(R+1)]
dp1 = [[0 for j in range(C+1)] for i in range(R+1)]
dp2 = [[0 for j in range(C+1)] for i in range(R+1)]
dp3 = [[0 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        dp3[i][j] = max(dp3[i][j], dp2[i][j]+I[i][j])
        dp2[i][j] = max(dp2[i][j], dp1[i][j]+I[i][j])
        dp1[i][j] = max(dp1[i][j], dp0[i][j]+I[i][j])
        dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j], dp1[i]
                          [j], dp2[i][j], dp3[i][j])
        dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])
        dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
        dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
        dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])


# print(*dp, sep=' \n')

ans = max(dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1])
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n-k+1):
  ans = max(ans, (sum(p[i:i+k])+k)/2)
print(ans)

### FIXED CODE ###

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

# 値ごとの期待値を取得
s = [0]*n
for i in range(n):
  s[i] = (p[i]+1)/2

# 期待値を累積していく
p = [0]*(n+1)
for i in range(1, n+1):
  p[i] = p[i-1] + s[i-1]

# 下記の方法で隣接する期待値合計を取得し、比較を行う。
# 隣接する期待値の合計　= 対象とする範囲の最大累積和　- 対象外範囲の最大累積和
ans = 0
for i in range(n-k+1):
  ans = max(ans, p[i+k] - p[i])

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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        for p, n in L.items():
            primes_a[a].setdefault(p, 0)
            b *= p ** (n - primes_a[a][p])
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, MOD-2, MOD) % MOD
    print(ans % MOD)



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

from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            li = len(s[i])
            di = d[i]
            for j in range(i, 3):
                lj = len(s[j])
                dij = di[j]
                for k in range(li):
                    notok = False
                    for ni in range(k, li):
                        nj = ni - k
                        if nj >= lj:
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            notok = True
                    dij[k] = notok
        f = lambda i, j, k: False if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if f(0, 1, x):
                    continue
                if f(1, 2, y):
                    continue
                if f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                if ans > now:
                    ans = now
    print(ans)
                
if __name__ == "__main__":
    main()

### FIXED CODE ###

from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            li = len(s[i])
            for j in range(i, 3):
                lj = len(s[j])
                for k in range(li):
                    ok = True
                    for ni in range(k, li):
                        nj = ni - k
                        if nj >= lj:
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            ok = False
                    d[i][j][k] = ok
        f = lambda i, j, k: True if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if not f(0, 1, x):
                    continue
                if not f(1, 2, y):
                    continue
                if not f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                ans = min(ans, now)
    print(ans)
                
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,A,B = map(int,input().split())
ans = list()
a = "a"
b = "b"
while N > 0:
    for _ in range(A):
        ans.append(a)
        N = N - 1
        if N == 0:
            print(ans.count(a))
            exit()
    for _ in range(B):
        ans.append(b)
        N = N - 1
        if N == 0:
            print(ans.count(a))
            exit()

### FIXED CODE ###

N,A,B = map(int,input().split())
if A == 0:
    print(A)
    exit()
n = N // (A + B)
nn = N % (A + B)
if n != 0 and nn <= A:
    print(int(A*n + nn))
elif n != 0 and nn > A:
    print(int(A*(n+1)))
elif n == 0 and N >= A:
    print(A)
elif n == 0 and N < A:
    print(N)
### BUGGY CODE ###

a, b, c = map(int, input() .split())
e = []
for i in range(a, b+1):
    d = i % c
    if d == 0:
        e.append(i)
print(len(e))

### FIXED CODE ###

a,b,x = map(int,input().split())
cb = b//x
ca = (a-1)//x
c = cb - ca
print(c)
### BUGGY CODE ###

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

S = list(map(int,input().split()))
T = list(map(int,input().split()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    l1 = sm[i-1][:]
    l2 = 0
    for j in range(1,M+1) :
        new = l1[j] + l2
        if S[i-1] == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l1[j-1] # dp = 0
        l2 = new
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

from itertools import combinations
lin = list(combinations(li, 3))
point = 0
for i in range(len(lin)):
    lin[i] = list(lin[i])
    lin[i].sort()
    if lin[i][2] < lin[i][0] + lin[i][1]:
        point += 1
print(point)

### FIXED CODE ###

from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

li.sort()

point = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        bi = bisect.bisect_left(li,li[i]+li[j])
        point += bi-j-1
print(point)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])
#根から計算した深さごとの要素数の最大値

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]
#葉から計算した最小値

#print(b)
#print(c)

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

for l in range(n):
    flag += 1 if d[l+1] < d[l] - a[l] or 2*d[l] - a[l] < d[l+1] else 0
    flag += 1 if a[l] + (d[l+1]+1)//2 > d[l] or d[l] > d[l+1] + a[l] else 0

ans = sum(d) if flag == 0 else -1
ans = -1 if n == 0 and a[0] > 1 else ans
ans = -1 if a[n] != d[n] else ans
print(ans)
#print(d)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

ans = sum(d) if flag == 0 else -1
ans = -1 if n == 0 and a[0] > 1 else ans
ans = -1 if a[n] != d[n] else ans
print(ans)
### BUGGY CODE ###


def main():
	S = list(input())
	n = len(S)
	ans = 0

	while(True):
		count = 0

		for i in range(0, n - 1):
			if(S[i] == 'B' and S[i+1] == 'W'):
				S[i], S[i+1] = S[i+1], S[i]
				count += 1

		if(count == 0):
			break

		ans += count
		
	print(ans)

if __name__ == "__main__":
	main()

### FIXED CODE ###


def main():
	S = input()
	n = len(S)
	ans = 0

	black = 0
	f_pos = 0
	l_pos = 0

	for i, c in enumerate(S):
		if(c == 'B'):			
			f_pos += i
			black += 1

	l_pos = sum(list(range(n-1, n-1-black, -1)))
	

	ans = l_pos - f_pos

		
	print(ans)

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

s = input()

lst = [0 for i in range(2019)]
lst[0] = 1

amari = 0
for i in range(1, len(s)+1):
    amari = (amari + int(s[-i])*(10**(i-1))) % 2019
    lst[amari] += 1

ans = 0
for i in range(2019):
    num = lst[i]
    ans += num * (num-1) // 2

print(ans)

### FIXED CODE ###

s = input()

lst = [0 for i in range(2019)]
lst[0] = 1

amari = 0
tmp = 1
for i in range(1, len(s)+1):
    amari = (amari + int(s[-i])*tmp) % 2019
    lst[amari] += 1
    tmp = (tmp*10) % 2019

ans = 0
for i in range(2019):
    num = lst[i]
    ans += num * (num-1) // 2

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

dic={}
s=set()
n=int(input())
d=[]
for i in range(n):
  d.append(input())
  s.add(d[-1])
mx=0
for w in s:
  dic[w]=d.count(w)
  mx=max(mx,dic[w])

for k,v in sorted(dic.items(),key=lambda x:(-x[1],x[0])):
  if mx==v:
    print(k)
    	


### FIXED CODE ###

dic={}
n=int(input())
d=[]
for i in range(n):
  d.append(input())
  if d[-1] in dic:
  	dic[d[-1]]+=1
  else:
    dic[d[-1]]=1
mx=max(dic.values())
for k,v in sorted(dic.items(),key=lambda x:(-x[1],x[0])):
  if mx==v:
    print(k)
### BUGGY CODE ###

INF = 10**10 - 1

#指定数分の複数の整数を順番に受けてリストに入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
Vsum = 0
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())
    Vsum += v[i]

#dpの初期化
dp = [[INF] * (Vsum+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for vv in range(1,Vsum+1):
        if v[i] > vv:
            dp[i][vv] = dp[i-1][vv]
        else:
            dp[i][vv] = min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
    #print(dp[i])

Vmax = 0
for vv in range(1,Vsum+1):
    if dp[N][vv] <= Wmax:
        Vmax = vv
print(Vmax)


### FIXED CODE ###

INF = 10**10 - 1

#指定数分の複数の整数を順番に受けてリストに入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
Vsum = 0
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())
    Vsum += v[i]

#dpの初期化
dp = [[INF] * (Vsum+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for vv in range(1,Vsum+1):
        if v[i] > vv:
            dp[i][vv] = dp[i-1][vv]
        else:
            dp[i][vv] = min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
    #print(dp[i])

Vmax = 0
for vv in range(1,Vsum+1):
    if dp[N][vv] <= Wmax:
        Vmax = vv
print(Vmax)
### BUGGY CODE ###

import numpy as np
k = int(input())

def gen(n):
    if n < 10:
        yield n
    else:
        for m in gen(n/10):
            yield m
        yield n%10
c = 9
if k >= 10:
    for i in range(10, 10**5):
        a = np.array( [int(i) for i in gen(i)])
        b = np.diff(a)
        if max(abs(b)) <= 1:
            c = c + 1
        if c == k:
            break

if k <= 10:
    print(k)
else:
    print(i)

### FIXED CODE ###

from collections import deque

k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    x = d.popleft()
    if x % 10 != 0:
        d.append(10 * x + x % 10 - 1)

    d.append(10 * x + x % 10)
    
    if x % 10 != 9:
        d.append(10 * x + x % 10 + 1)

print(x)
### BUGGY CODE ###

from copy import deepcopy
def main():
    h, n = map(int, input().split())
    
    inf = float('inf')
    dp = [inf] * (h + 1)
    dp[0] = 0
    for _ in range(n):
        a, b = map(int, input().split())
        dp_c = deepcopy(dp)
        for i1 in range(h + 1):
            if i1 <= a:
                dp[i1] = min(b, dp_c[i1])
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - a] + b)
    print(dp[h])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

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

from heapq import heappush, heappop, heapify
import math
def solve():
	n , k= map(int, input().strip().split())
	a= [(-int(x),1,int(x)) for x in input().strip().split()]
	heapify(a)
	for i in range(k):
		x,cnt,orig = heappop(a)
		heappush(a,(-((orig+cnt)//(cnt+1)),cnt+1,orig))
	return -(heappop(a)[0])


print(solve())

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import math
def check(a,mid,k):
	cnt = 0
	for x in a:
		cur_cnt = (x+mid-1)//mid - 1
		cnt+=cur_cnt
		if cnt > k:
			return False
	return True

def solve():
	n , k= map(int, input().strip().split())
	a= [int(x) for x in input().strip().split()]
	l = 0
	r = 10**9+20
	while r-l > 1:
		mid = (r+l)//2
		if check(a,mid,k):
			r = mid
		else:
			l = mid
	return l+1
 
print(solve())