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

n,m = map(int,input().split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(n):
	a_dash,b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)

for i in reversed(range(m)):
	l_dash = [ b[j] for j in range(count,len(a)) if a[j]+i==m ]
	l.extend(l_dash)
	count += len(l_dash)
	if len(l) != 0:
		ans += max(l)
		l.pop(l.index(max(l)))

print(ans)

### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a[:k])
for i in range(n-k):
	t=sum(a[i+1:k+i+1])
	print('YNeos'[s>=t::2])
	s=t

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a[:k])
for i in range(n-k):
	t=s-a[i]+a[k+i]
	print('YNeos'[s>=t::2])
	s=t
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans=0
num=[]
if len(set(a))-k <0:
    print(0)
else:
    for x in set(a):
        num.append(a.count(x))
    num.sort()
    for i in range(len(set(a))-k):
        ans+=num[i]
    print(ans)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
ans=0
num=[]
seta=set(a)
if len(seta)-k <0:
    print(0)
else:
    for x in seta:
        num.append(c[x])
    num.sort()
    for i in range(len(seta)-k):
        ans+=num[i]
    print(ans)
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()


def main():
    N, M, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]

    a, b = [0], [0]
    for i in range(N):
        a.append(sum(A[:i+1]))

    for i in range(M):
        b.append(sum(B[:i+1]))

    ans, j = 0, M
    for i in range(len(a)):
        if a[i] > K:
            break
        while a[i] + b[j] > K:
            j -= 1
        ans = max(ans, i + j)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()


def main():
    N, M, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]

    a, b = [0], [0]
    for i in range(N):
        a.append(a[i] + A[i])

    for i in range(M):
        b.append(b[i] + B[i])

    ans, j = 0, M
    for i in range(len(a)):
        if a[i] > K:
            break
        while a[i] + b[j] > K:
            j -= 1
        ans = max(ans, i + j)

    print(ans)


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

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
from numba import jit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
c = Counter(a)

se = set()

@jit
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in a:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
            break
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
from numba import jit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
b = list(set(a))
b.sort()
c = Counter(a)

se = set()

@jit
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in b:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
            break
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)
### BUGGY CODE ###

# coding: utf-8
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

N = ir()
A = lr()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = 0
for a in A:
    answer += lcm // a
    answer %= MOD

print(answer % MOD)
# np.int64とint型の違いに注意

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

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

n=int(input())
#それぞれ長さはn-1
a=[[(j-1,i) if j-1<i else (i,j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
#最大n(n-1)/2回
ans=0
while len(d):
    ans+=1
    nextd=[]
    cleard=[]
    #一個も同じのなかったらむり
    g=True
    for i in d:
        if d[i]==2:
            g=False
            e,f=i
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
    if g:
        exit(print(-1))       
    for i in nextd:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for i in cleard:
        d.pop(i)
print(ans)

### FIXED CODE ###

from collections import deque
#わからない、テストケース
n=int(input())
#それぞれ長さはn-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
#最大n(n-1)/2回
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
    ans+=1
    #一個も同じのなかったらむり
    g=True
    changeable2=deque()
    for i in changeable1:
        if d[i]==2:
            g=False
            e,f=i//n,i%n
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
                changeable2.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
                changeable2.append(a[f][b[f]])
    if g:
        exit(print(-1))
    ln,lc=len(nextd),len(cleard)  
    for _ in range(ln):
        i=nextd.popleft()
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for _ in range(lc):
        i=cleard.popleft()
        #print(i)
        #print(d)
        d.pop(i)
    changeable1=set(changeable2)
print(ans)
### BUGGY CODE ###

N = int(input())
X = []

for i in range(1,10):
    a = []
    for j in range(1,10):
        c = 0
        for k in range(1,N+1):
            if (str(k)[0] == str(i))&(str(k)[-1] == str(j)):
                c +=1
        a.append(c)
    X.append(a)
    
ans = 0

for i in range(9):
    for j in range(9):
        ans += X[i][j]*X[j][i]
print(ans)

### FIXED CODE ###

N = int(input())
X = [[0 for j in range(10)] for i in range(10)]

for k in range(1,N+1):
    X[int(str(k)[0])][int(str(k)[-1])] +=1

Ans = 0
for i in range(10):
    for j in range(10):
        Ans += X[i][j]*X[j][i]
print(Ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, k = map(int, input().split())
dp = [0] * n
dp[0] = 1
dp[1] = -1
delta = []
for _ in range(k):
    l, r = map(int, input().split())
    delta.append((l, 1))
    delta.append((r+1, -1))

total = 0
for i in range(n):
    total += dp[i]
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
print(total % MOD)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, k = map(int, input().split())
dp = [0] * n
dp[0] = 1
dp[1] = -1
delta = []
for _ in range(k):
    l, r = map(int, input().split())
    delta.append((l, 1))
    delta.append((r+1, -1))

total = 0
for i in range(n):
    total += dp[i]
    total %= MOD
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
        dp[i + p] %= MOD
print(total % MOD)
### BUGGY CODE ###

N = int(input())

E = []
es = [[] for _ in range(N)]
for j in range(N):
    s = input()
    e = []
    for i, c in enumerate(s):
        e.append(1 if c=="1" else float("inf"))
        if c=="1":
            es[i].append(j)
    E.append(e)

# http://prd-xxx.hateblo.jp/entry/2017/10/13/004256

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

if not dfs(0, 1):
    print(-1)
    exit()

for i in range(N):
    E[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            E[i][j] = min(E[i][j], E[i][k]+E[k][j])

ans = 0
for e in E:
    ans = max(ans, max(e))
print(ans+1)


### FIXED CODE ###

N = int(input())

E = []
es = [[] for _ in range(N)]
for j in range(N):
    s = input()
    e = []
    for i, c in enumerate(s):
        e.append(1 if c=="1" else float("inf"))
        if c=="1":
            es[i].append(j)
    E.append(e)

# http://prd-xxx.hateblo.jp/entry/2017/10/13/004256

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

if not dfs(0, 1):
    print(-1)
    exit()

for i in range(N):
    E[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            E[i][j] = min(E[i][j], E[i][k]+E[k][j])

ans = 0
for e in E:
    ans = max(ans, max(e))
print(ans+1)
### BUGGY CODE ###

#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools


N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
Q=int(input())
l=[]
for i in range(Q):
    #print(A)
    B,C = map(int,input().split())
    a=True
    while a==True:
        try:
            ind=A.index(B)
            A[ind]=C
            #print(A)
        except:
            a=False
    #print(A)
    l.append(sum(A))
for i in l:
    print(i)


### FIXED CODE ###

#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools
import collections

N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
Q=int(input())
c=collections.Counter(A)
s=sum(A)
for i in range(Q):
    #print(A)
    B,C = map(int,input().split())
    if c[B]:
        s += (C-B)*c[B]
        c[C] += c[B]
        c[B] = 0

    print(s)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 1
for i in l:
    ans*=i
if ans>10**18: print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 1
for i in l:
    ans*=i
    if(ans==0):
        ans = 0
        break
    if ans>10**18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

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


### FIXED CODE ###

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

N = int(input())
A = list(map(int, input().split()))
AP = []
AM = []
for i in range(N):
  plus = i+1 + A[i]
  AP.append(plus)
  minus = i+1 - A[i]
  AM.append(minus)

ans = 0 

for j in range(N):
  for k in range(j+1, N):
    if AM[k] <= 0:
      continue
    if AP[j] == AM[k]:
      ans += 1
      
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
AM = []
AP = []
AMlist = [0] * N
APlist = [0] * N

for i in range(N):
  plus = i+1 + A[i]
  AP.append(plus)  
  if AP[i] <= N:
    APlist[AP[i]-1] += 1
  minus = i+1 - A[i]
  AM.append(minus)
  if AM[i] > 0 and AM[i] <= N:
    AMlist[AM[i]-1] += 1
    
ans = 0

for j in range(N):
  ans += APlist[j] * AMlist[j]

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

# -*- coding: utf-8 -*-        
import numpy as np

s = input()
dstx, dsty = list(map(int,input().split()))
x = []
y = []
tmp = 0
xy = 0
for i in range(len(s)):
    if(s[i]=='F'):
        tmp += 1
    elif(s[i]=='T' and xy==0):
        x.append(tmp)
        tmp = 0
        xy = 1
    elif(s[i]=='T' and xy==1):
        y.append(tmp)
        tmp = 0
        xy = 0
else:
    if(xy==0):
        x.append(tmp)
    else:
        y.append(tmp)
        
dpx = np.zeros((len(x),16002),dtype='bool')
dpy = np.zeros((len(y)+1,16002),dtype='bool')
dpx[0][8001+x[0]] = True
dpy[0][8001] = True
for i in range(1,len(x)):
    for j in range(0,16002):
        if(j-x[i]<0):
            dpx[i][j] = dpx[i-1][j+x[i]]
        elif(j+x[i]>16001):
            dpx[i][j] = dpx[i-1][j-x[i]]
        else:
            dpx[i][j] = dpx[i-1][j-x[i]] or dpx[i-1][j+x[i]]
for i in range(1,len(y)+1):
    for j in range(0,16002):
        if(j-y[i-1]<0):
            dpy[i][j] = dpy[i-1][j+y[i-1]]
        elif(j+y[i-1]>16001):
            dpy[i][j] = dpy[i-1][j-y[i-1]] 
        else:
            dpy[i][j] = dpy[i-1][j-y[i-1]] or dpy[i-1][j+y[i-1]]

if(dpx[-1][8001+dstx] and dpy[-1][8001+dsty]):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

s = input()
dstx, dsty = list(map(int,input().split()))
x = []
y = []
tmp = 0
xy = 0
for i in range(len(s)):
    if(s[i]=='F'):
        tmp += 1
    elif(s[i]=='T' and xy==0):
        x.append(tmp)
        tmp = 0
        xy = 1
    elif(s[i]=='T' and xy==1):
        y.append(tmp)
        tmp = 0
        xy = 0
else:
    if(xy==0):
        x.append(tmp)
    else:
        y.append(tmp)
dpx = [{} for i in range(len(x))]
dpy = [{} for i in range(len(y)+1)]
dpx[0][x[0]] = True
dpy[0][0] = True
for i, dx in enumerate(x[1:]):
    for j in dpx[i]:
        dpx[i+1][j+dx] = True
        dpx[i+1][j-dx] = True
if(dstx not in dpx[-1]):
    print('No')
    sys.exit()
for i, dy in enumerate(y):
    for j in dpy[i]:
        dpy[i+1][j+dy] = True
        dpy[i+1][j-dy] = True
    
if(dstx not in dpx[-1] or dsty not in dpy[-1]):
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

import itertools

T = list(input())
location_q = []
Tstr = []
count_D_PD = []
count_q = T.count('?')

for s in range(len(T)):
    if T[s] == '?':
        location_q.append(s)

for i in itertools.product(['P','D'], repeat=count_q):
    for j in range(len(location_q)):
        T[location_q[j]] = i[j]
    Tstr.append(''.join(T))
# print(Tstr)

for k in range(len(Tstr)):
    count_D_PD.append(Tstr[k].count('D') + Tstr[k].count('PD'))
# print(count_D_PD)
# print(max(count_D_PD))
# print(count_D_PD.index(max(count_D_PD)))
print(Tstr[count_D_PD.index(max(count_D_PD))])


### FIXED CODE ###

T = list(input())
for i in range(len(T)):
    if T[i] == '?':
        T[i] = 'D'

print(''.join(T))
### BUGGY CODE ###

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

for i in range(1, n+1):
    cnt = 0
    for j in a:
        if i == j:
            cnt += 1
    print(cnt)


### FIXED CODE ###

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

cnt = {}
for i in a:
    cnt.setdefault(i, 0)
    cnt[i] += 1

for i in range(1, n+1):
    cnt.setdefault(i, 0)
    print(cnt[i])
### BUGGY CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 1 << 30
dp = [INF]*N
dp[0] = 0
for i, (d, h) in enumerate(zip(dp, H)):
    for k in range(1, K+1):
        if i+k >= N:
            break
        dp[i+k] = min(dp[i+k], d + abs(H[i+k]-h))

print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
dp = [1<<30]*(N)
dp[0] = 0
 
for i in range(1, N):
  dp[i] = min((dp[j]+abs(h[i]-h[j])) for j in range(max(0, i-K), i))
 
print(dp[N-1])
### BUGGY CODE ###

n=int(input())
s = input()

dp=[{"R":-5000,"G":-5000,"B":-5000}]

count = 0
for num, i in enumerate(s):
    new_dp=[]
    for j in dp:
        #print(j)
        if not(j in new_dp):
            new_dp.append(j)
        if i=="R":
            if j[i]==-5000 and not(abs(j["G"]-j["B"])==num-max(j["G"],j["B"])):
                if j["G"]>=0 and j["B"]>=0:
                    count += 1
                else:
                    new_dp.append({"R":num,"G":j["G"],"B":j["B"]})
                
        if i=="G":
            if j[i]==-5000 and not(abs(j["R"]-j["B"])==num-max(j["R"],j["B"])):
                if j["R"]>=0 and j["B"]>=0:
                    count += 1
                else:
                    new_dp.append({"R":j["R"],"G":num,"B":j["B"]})
            
        if i=="B":
            if j[i]==-5000 and not(abs(j["R"]-j["G"])==num-max(j["R"],j["G"])):
                if j["R"]>=0 and j["G"]>=0:
                    count += 1
                else:
                    new_dp.append({"R":j["R"],"G":j["G"],"B":num})
                    
    dp = new_dp
    #print(i,dp)

print(count)

### FIXED CODE ###

n=int(input())
s = input()

R=[]
G=[]
B=[]

for i in range(n):
    if s[i]=="R":
        R.append(i)
    elif s[i]=="G":
        G.append(i)
    else:
        B.append(i)

#print(B)
count = len(R)*len(G)*len(B)
d={}
for i in R:
    for j in G:
        big = max(i,j)
        small = min(i,j)
        
        x = 2*big-small
        y = 2*small-big
        z = (big+small)/2
        
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
        if y in d:
            d[y] += 1
        else:
            d[y] = 1
        if z%1==0:
            if z in d:
                d[z] += 1
            else:
                d[z] = 1
        
        #if 2*big-small in B:
            #count -= 1
            #print(i,j)
            #print("hoi")
        #if 2*small-big in B:
            #count -= 1
            #print(i,j)
        #if (big+small)/2 in B:
            #print((big+small)/2)
            #count -= 1
            #print(i,j)
    
for i in B:
    if i in d:
        count -= d[i]
    
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# なんかおかしい！！
import math
import sys
import itertools
import numpy as np


# なんこか入力
x,y,z,k = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()
#cake = [[0 for i in range(3)] for j in range(3000)]
#cake[0][0]=x-1
#cake[0][1]=y-1
#cake[0][2]=z-1
#print(a[x-1]+b[y-1]+c[z-1])
#print(a[cake[0][0]],b[cake[0][1]],c[cake[0][2]])
s = [[x-1,y-1,z-1]]
t = [[-1,-1,-1] for i in range(3*k)]
t[0] = [x-1,y-1,z-1]
t_a = 1
#print(s)

for i in range(0,k):
    ma = 0
    temp = [-1,-1,-1]
    for j in s:
        if ma <= a[j[0]]+b[j[1]]+c[j[2]] :
            temp = j
            ma = a[j[0]]+b[j[1]]+c[j[2]]
#    print(temp)
    print(a[temp[0]]+b[temp[1]]+c[temp[2]])
#    print(a[temp[0]],b[temp[1]],c[temp[2]])
    s.remove(temp)
#    print("s=",s)
#    print("t=",t)
#    print(temp)
    if temp[0] > 0:
        if [temp[0]-1,temp[1],temp[2]] in t:
            pass
        else:
            s.append([temp[0]-1,temp[1],temp[2]])
            t[t_a] = [temp[0]-1,temp[1],temp[2]]
            t_a += 1
    if temp[1] > 0:
        if [temp[0],temp[1]-1,temp[2]] in t:
            pass
        else:
            s.append([temp[0],temp[1]-1,temp[2]])
            t[t_a] = [temp[0],temp[1]-1,temp[2]]
            t_a += 1
    if temp[2] > 0:
        if [temp[0],temp[1],temp[2]-1] in t:
            pass
        else:
            s.append([temp[0],temp[1],temp[2]-1])
            t[t_a] = [temp[0],temp[1],temp[2]-1]
            t_a += 1


### FIXED CODE ###

# -*- coding: utf-8 -*-
# ヒープキューを使う

import math
import sys
import itertools
import numpy as np
import heapq
 
# なんこか入力
x,y,z,k = map(int, input().split())
 
# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()

h = [] # heap
g = set() #使用済み

heapq.heappush(h,(-(a[x-1]+b[y-1]+c[z-1]),x-1,y-1,z-1))
g.add((x-1,y-1,z-1))

#print(h)

for i in range(k):
#    heapq.heapify(h)
    temp =[]
    temp = heapq.heappop(h)
    print(-temp[0])
    for j in range(3):
        if temp[j+1]==0:
            continue
        if j == 0:
            temp2 = (-(a[temp[1]-1]+b[temp[2]]+c[temp[3]]),temp[1]-1,temp[2],temp[3])
        elif j == 1:
            temp2 = (-(a[temp[1]]+b[temp[2]-1]+c[temp[3]]),temp[1],temp[2]-1,temp[3])
        else:
            temp2 = (-(a[temp[1]]+b[temp[2]]+c[temp[3]-1]),temp[1],temp[2],temp[3]-1)
        if (temp2[1],temp2[2],temp2[3]) in g:
            continue
        heapq.heappush(h,temp2)
        g.add((temp2[1],temp2[2],temp2[3]))
### BUGGY CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
maxi = 0
Npower = 0
diff = 0
S = N
while S/10 >= 1:
    Npower += 1
    S /=10
if Npower >= 8: 
    for i in range(0,10**7):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
    for i in range(N-10**6-10**5-10**4-10**3-10**2,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
else:
    for i in range(0,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
print(max(maxi,0))


### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))