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

x, y, z, k = map(int, input().split())
a_s = list(map(int, input().split()))
bs = list(map(int, input().split()))
cs = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = 0
flag = True
minlist = 0
for a in a_s:
    if minlist > (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist > (a + b + cs[0]):
            break
        for c in cs:
            abc = a + b +c
            if flag and i > k:
                minlist = min(list)
                flag = False
            if minlist > abc:
                break
            list.append(a + b + c)
            i += 1
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### 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()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]

cnt = 0
for i, x in enumerate(s[:-1]):
    for y in s[i+1:]:
        if x == y:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter

N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]
c = Counter(sorted(s))
ret = int(sum([x * (x-1) / 2 for x in c.values()]))
print(ret)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def dfs(h, w):
    ans = 0
    for hp in range(h - 1, 0 - 1, -1):
        if S[hp][w] == '.':
            ans += 1
        else:
            break
    for wp in range(w - 1, 0 - 1, -1):
        if S[h][wp] == '.':
            ans += 1
        else:
            break
    for hp in range(h + 1, H, 1):
        if S[hp][w] == '.':
            ans += 1
        else:
            break
    for wp in range(w + 1, W, 1):
        if S[h][wp] == '.':
            ans += 1
        else:
            break
    return ans + 1


ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            ans = max(dfs(h, w), ans)

print(ans)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-(h + 1)] = (D[-h] + 1) * S[-(h + 1)]

for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -(w + 1)] = (R[:, -w] + 1) * S[:, -(w + 1)]

print(np.max(U + D + L + R) - 3)
### BUGGY CODE ###

import copy

n = int(input())

a = [0] + list(map(int,input().split())) + [0]

#print(a)


for i in range(1,len(a)-1):
    ans = 0
    for j in range(1,len(a)):
        if(j-1 != i and j != i):
            ans += abs(a[j]-a[j-1])
        elif(j == i):
            ans += abs(a[j+1]-a[j-1])
            j+=1
    print(ans)

    

### FIXED CODE ###

import copy

n = int(input())

a = [0] + list(map(int,input().split())) + [0]

#print(a)
anst = 0
for j in range(1,len(a)):
    anst += abs(a[j]-a[j-1])

for j in range(1,len(a)-1):
    ans = anst
    ans -= abs(a[j-1]-a[j]) + abs(a[j]-a[j+1])
    ans += abs(a[j-1]-a[j+1])
    print(ans)
### BUGGY CODE ###

a,b,x=[int(i) for i in input().split()]
count=0
count=['_' for i in range(a,b+1) if i%x==0]
print(len(count))
'''for i in range(a,b+1):
    if(i%x==0):
        count+=1
print(count)'''


### FIXED CODE ###

a,b,x=[int(i) for i in input().split()]
print(b//x-(a-1)//x)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
def findans(start,end,li):
  #print("HI")
  if(start>=end):
    return 0
  if(dp[start][end]!=-1):
    return dp[start][end]
  ans = INF
  for k in range(start,end+1):

      ans=min(findans(start,k,li)+findans(k+1,end,li),ans)
      dp[start][end]=ans+sum(li[start:end+1])
  return dp[start][end]
n=int(input())
li=[int(k) for k in input().split()]
dp=[[-1 for i in range(n)]for k in range(n)]
print(findans(0,n-1,li))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

def findsum(li):

    for i in range(1,len(li)+1):
        tot[i]=tot[i-1]+li[i-1]
    #print(tot)

def findans(start,end,li):
  global tot
  #print("HI")
  if(start>=end):
    return 0
  if(dp[start][end]!=-1):
    return dp[start][end]
  ans = INF
  for k in range(start,end):


      ans=min(findans(start,k,li)+findans(k+1,end,li),ans)
  dp[start][end]=ans+(tot[end+1]-tot[start])
  return dp[start][end]
n=int(input())
li=[int(k) for k in input().split()]
tot=[0]*(len(li)+1)
findsum(li)
dp=[[-1 for i in range(n)]for k in range(n)]
print(findans(0,n-1,li))
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 0
N = read_a_int()
A = []
for a in read().split():
    A.append(int(a))
    n = max(n, len(bin(int(a))) - 2)


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * n_1) % MOD
        else:
            ret += (((2**i) % MOD) * (n_1_max - n_1)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import math
import itertools


# 与えられた数値の桁数と桁値の総和を計算する.
def calc_digit_sum(num):
    digits = sums = 0
    while num > 0:
        digits += 1
        sums += num % 10
        num //= 10
    return digits, sums


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

MOD = 10 ** 9 + 7

answer = 0
t = itertools.combinations(arr, 2)
for i in t:
    answer = (answer + i[0] * i[1]) % MOD

print(answer)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
sums = sum(arr)

answer = 0
for num in arr:
    sums -= num
    answer = (answer + (sums * num)) % mod

print(answer)
### BUGGY CODE ###

n = int(input())
print(0,flush=True)

prev = input()
if prev=='Vacant': exit()

now=[]

def isok(ans, should_change):
    print(ans,flush=True)
    now = input()

    if now == 'Vacant': exit()

    if (now!=prev and should_change)or(now==prev and not should_change):
        return True
    else:
        return False

ok = n
ng = 1

while ok - ng > 1:
    m = (ok+ng)//2
    should_change = (m-ng)%2!=0
    if isok(m, should_change):
        prev=now
        ok = m
    else:
        prev=now
        ng = m


### FIXED CODE ###

n = int(input())
print(0,flush=True)

prev = input()
if prev=='Vacant': exit()
zero = prev
now=[]

def isok(ans, odd_diff):
    print(ans,flush=True)
    now = input()

    if now == 'Vacant': exit()

    if (now==zero and odd_diff)or(now!=zero and not odd_diff):
        return True
    else:
        return False

ok = n-1 #ok以前にVacantが存在
ng = 0 #ng以前にVacantは存在しない

while ok - ng > 1:
    m = (ok+ng)//2
    odd_diff = (m%2==1)
    if isok(m, odd_diff):
        ok = m
    else:
        ng = m

print(ok,flush=True)
exit()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
l = []
total = 0

m = max(a)
mi = min(a)

if mi == m:
    total = ((len(a)-1)*(len(a)-2))/2
    for _ in range(n):
        print(int(total))

else:
    for i in range(mi, m+1):
        r = a.count(i)
        if r:
            total += (r*(r-1))/2
        l.append(r)

    #print(l)
    #print(total)

    for k in range(n):
        score = total
        if l[a[k]-1]:
            score -= (l[a[k]-1]-1)
        print(int(score))


### FIXED CODE ###

from collections import Counter

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

c = Counter(a)

for r in list(c.values()):
    total += (r*(r-1))/2

#print(l)
#print(total)

for i in a:
    score = total - (c[i]-1)
    print(int(score))
### BUGGY CODE ###

import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    syou = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if prov_cost > syou:
        break
      if d[src] < prov_cost:
                continue
      for dest in range(num_v):
        you = cost[src][dest]
        if you != float('inf') and d[dest] > d[src] + you:
          d[dest] = d[src] + you
          heapq.heappush(q, (d[dest], dest))
          syou = max(d[dest],syou)
    return d


from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

### FIXED CODE ###

import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    su.append([x1-1,y1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
 
 
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

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

n=int(input())
a=list(map(int,input().split()))
answer=1
for i in range(n):
    answer*=a[i]
if answer>10**18:
    answer=-1
print(answer)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
answer=1
for i in range(n):
    answer*=a[i]
    if answer>10**18:
        answer=-1
        break
if a.count(0)>0:
    answer=0
print(answer)
### BUGGY CODE ###

L,R = map(int,input().split())
ans = 2019
for i in range(L,R+1):
  for j in range(i+1,R+1):
    if (i*j)%2019 < ans:
      ans = (i*j) % 2019
      if ans == 0:
        break
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
ans = 2019

if R*(R-1)<2019:
  print(R*(R-1))
  exit(0)
else:
  if R == L+1:
    print((R*L)%2019)
    exit(0)
  else:
    r =673 - L % 673
    if L+r <= R:
      print("0")
      exit(0)
    else:
      for i in range(L,R+1):
        for j in range(i+1,R+1):
          if (i*j)%2019 < ans:
            ans = (i*j) % 2019
            if ans == 0:
              break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

MAX=max(abs(A[0]),abs(A[-1]))
OK=-MAX**2-1
NG=MAX**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0

    #print(OK,NG,mid,SC)

    if SC<=K-1:
        OK=mid
    else:
        NG=mid
        
print(OK)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

M=[]
Z=[]
P=[]

for a in A:
    if a<0:
        M.append(-a)
    elif a==0:
        Z.append(a)
    else:
        P.append(a)

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)
### BUGGY CODE ###

import itertools as it

num = int(input())

item_number = num//100

res_list = []
candi_list = list(it.combinations_with_replacement([100, 101, 102, 103, 104, 105], item_number))
candi_ans_list = [sum(item) for item in candi_list]

if num in candi_ans_list:
    print(1)
else:
    print(0)

### FIXED CODE ###

line = input()

if int(line) >= 100:
    num = int(line[-2:])
    item_number = int(line[:-2])



    res_list = []
    a = 5
    while True:
        if num == 0:
            break
        for _ in range(num//a):
            res_list.append(a)

        num = num % a

        if 1<= num <= 4:
            res_list.append(num)
            break


    # print(res_list)

    if len(res_list) > item_number:
        print(0)
    else:
        print(1)

else:
    print(0)
### BUGGY CODE ###

# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[0 for _ in range(3001)] for _ in range(3001)]


def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result)


def solve(S, T):
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            if S[i - 1] != T[j - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i-1][j-1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    while dp[i][j] != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            result += S[i-1]
            i -= 1
            j -= 1
    return "".join(reversed(result))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[0 for _ in range(3001)] for _ in range(3001)]


def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result)


def solve(S, T):
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            if S[i - 1] != T[j - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i-1][j-1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    while dp[i][j] != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            result += S[i-1]
            i -= 1
            j -= 1
    return "".join(reversed(result))


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

n, k = map(int, input().split())
A = list(map(int, input().split()))
c = 1
P = [1]
for i in range(1,k+1):
    c = A[c-1]
    if i == k:
        print(c)
        exit(0)
    if c in P:
        roop_start = P.index(c)
        roop_num = i- roop_start
        a = (k - roop_start) %  roop_num
        b = P[a + roop_start]
        print(b)
        exit(0)
    P.append(c)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = A[now-1]
    A = [A[a-1] for a in A]
print(now)
### BUGGY CODE ###

#!/usr/bin/env python3

from copy import deepcopy

ABMAX = 400
HUGE = 10 ** 12

def main():
    n, ma, mb = map(int, input().split())
    sold = []
    for i in range(n):
        a, b, c = map(int, input().split())
        sold.append((a, b, c))
    mincost = dp(sold, n)
    print(find_mincost(mincost, ma, mb))

def find_mincost(mincost, ma, mb):
    for mult in range(1, ABMAX):
        if ma * mult > ABMAX:
            break
        if mb * mult > ABMAX:
            break
        if mincost[ma * mult][mb * mult] < HUGE:
            return mincost[ma * mult][mb * mult]
    return -1

def dp(sold, n):
    # mincost[a][b]: Minimum cost of achieving a, b
    mincost = [[HUGE for b in range(ABMAX + 1)] for a in range(ABMAX + 1)]
    mincost[0][0] = 0
    for a, b, c in sold:
        mincost = update(mincost, a, b, c)
    return mincost

def update(prevcost, a, b, c):
    mincost = deepcopy(prevcost)
    for ia in range(ABMAX + 1):  # 配る
        for ib in range(ABMAX + 1):
            na = ia + a
            nb = ib + b
            if na <= ABMAX and nb <= ABMAX:
                mincost[na][nb] = min(mincost[na][nb], prevcost[ia][ib] + c)
    return mincost

main()


### FIXED CODE ###

#!/usr/bin/env python3

from copy import deepcopy

ABMAX = 400
HUGE = 10 ** 12

def main():
    n, ma, mb = map(int, input().split())
    sold = []
    for i in range(n):
        a, b, c = map(int, input().split())
        sold.append((a, b, c))
    mincost = dp(sold, n)
    print(find_mincost(mincost, ma, mb))

def find_mincost(mincost, ma, mb):
    res = HUGE
    for mult in range(1, ABMAX):
        if ma * mult > ABMAX:
            break
        if mb * mult > ABMAX:
            break
        res = min(res, mincost[ma * mult][mb * mult])
    return -1 if res == HUGE else res

def dp(sold, n):
    # mincost[a][b]: Minimum cost of achieving a, b
    mincost = [[HUGE for b in range(ABMAX + 1)] for a in range(ABMAX + 1)]
    mincost[0][0] = 0
    for a, b, c in sold:
        mincost = update(mincost, a, b, c)
    return mincost

def update(prevcost, a, b, c):
    mincost = deepcopy(prevcost)
    for ia in range(ABMAX + 1):  # 配る
        for ib in range(ABMAX + 1):
            na = ia + a
            nb = ib + b
            if na <= ABMAX and nb <= ABMAX:
                mincost[na][nb] = min(mincost[na][nb], prevcost[ia][ib] + c)
    return mincost

main()
### BUGGY CODE ###

n, k = map(int, input().split())
*a, = map(int, input().split())
d = {}
for i in a:
    d[i] = d.get(i, 0)+1
a.sort(key=lambda x: d[x])
b = sorted(set(a), key=a.index)
cnt = len(b)
ans = 0
for i in b:
    if cnt <= k:
        break
    ans += d[i]
    cnt -= 1
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
*a, = map(int, input().split())
d = {}
for i in a:
    d[i] = d.get(i, 0)+1
cnt = len(d)
ans = 0
for _, i in sorted(d.items(), key=lambda x: x[1]):
    if cnt <= k:
        break
    ans += i
    cnt -= 1
print(ans)
### BUGGY CODE ###

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

h = []
for _ in range(N):
    h.append(int(input()))

h.sort()

iter = len(h) - K

c_hmin = 99999999999999999999999999999999

for i in range(iter+1):
    cell = h[i: K + i]
    hmin = cell[-1] - cell[0]
    if c_hmin > hmin:
        c_hmin = hmin

print(c_hmin)

### FIXED CODE ###

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

h = []
for _ in range(N):
    h.append(int(input()))

h.sort()

iter = len(h) - K

c_hmin = 99999999999999999999999999999999

for i in range(iter+1):

    hmin = h[K+i-1] - h[i]
    if c_hmin > hmin:
        c_hmin = hmin

print(c_hmin)