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

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()
    k = ni()

    substring = set()
    for i in range(97, 97+26):
        word = chr(i)

        for j in range(len(s)):
            if s[j] == word:
                tmp = s[j:]

                while len(tmp) > 0:
                    if tmp in substring:
                        break
                    else:
                        substring.add(tmp)
                        tmp = tmp[:-1]

        if len(substring) >= k:
            break

    ans = list(substring)
    ans.sort()

    print(ans[k-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()
    k = ni()

    substring = set()
    for i in range(97, 97 + 26):
        word = chr(i)

        for j in range(len(s)):
            if s[j] == word:
                tmp = s[j:j + k]

                while len(tmp) > 0:
                    substring.add(tmp)
                    tmp = tmp[:-1]

        if len(substring) >= k:
            break

    ans = list(substring)
    ans.sort()

    print(ans[k - 1])


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

a=input()
n=len(a)
ansset=[a]
from itertools import combinations
for i,j in combinations(range(n),2):
    ansset.append(a[:i]+a[i:j+1][::-1]+a[j+1:])
print(len(set(ansset)))

### FIXED CODE ###

a=input()
n=len(a)
dupli=0
from collections import Counter
c=Counter(a)
for word,num in c.most_common():
    dupli+=num*(num-1)//2
print(n*(n-1)//2-dupli+1)
### BUGGY CODE ###

import numpy as np

K = int(input())
s = len(input())
MOD = 10**9 + 7

def fft_convolve(f, g):

    Lf, Lg = f.shape[-1], g.shape[-1]
    Lg = g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fh, fl = f >> 15, f & (1 << 15) - 1
    gh, gl = g >> 15, g & (1 << 15) - 1

    def conv(f, g):
        Ff = np.fft.rfft(f, fft_len)
        Fg = np.fft.rfft(g, fft_len)
        h = np.fft.irfft(Ff * Fg)
        return np.rint(h)[..., :L].astype(np.int64) % MOD

    x = conv(fl, gl)
    z = conv(fh, gh)
    y = conv(fl + fh, gl + gh) - x - z
    return (x + (y << 15) + (z << 30)) % MOD

def coef_of_generating_function(P, Q, N):
    assert Q[0] == 1 and len(Q) == len(P) + 1

    def convolve(f, g):
        return fft_convolve(f, g)

    while N:
        Q1 = np.empty_like(Q)
        Q1[::2] = Q[::2]
        Q1[1::2] = MOD - Q[1::2]
        P = convolve(P, Q1)[N & 1::2]
        Q = convolve(Q, Q1)[::2]
        N >>= 1
    return P[0]

den = np.array([1, -26])
for _ in range(s):
  den = fft_convolve(den, np.array([1, -25]))

num = np.zeros_like(den)[:-1]
num[0] = 1

print(coef_of_generating_function(num, den, K))

### FIXED CODE ###

K = int(input())
S = input()
s = len(S)
L = []

mod = 10 ** 9 + 7
N = 2 * 10**6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, N + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

for i in range(K+1):
  L.append( cmb(i+s-1, s-1) * pow(25, i, mod) % mod )

ans = []

for i, x in enumerate(L):
  if i == 0:
    ans.append(x)
  else:
    ans.append( ( ans[i-1]*26%mod + x ) % mod )

print(ans[K])
### BUGGY CODE ###

H, W, K = map(int, input().split())

G = [list(input()) for _ in range(H)]

ans = H * W

def calc(lst):
    group = sum(lst) + 1
    tmp = [[0] * W for _ in range(group)] #何グループに分かれるか
    k = 0
    for j in range(W):
        for i in range(H):
            if G[i][j] == '1':
                tmp[k][j] += 1
            if lst[i] == 1 or i == H - 1:
                k = (k + 1) % group
    
    cut = group - 1
    for j in range(W):
        flag = False
        for i in range(group):
            if tmp[i][j] > K:
                return 10 ** 9
            if j < W - 1:
                if tmp[i][j] + tmp[i][j + 1] > K: #次の戸合わせてKより大きくなるなら切る
                    flag = True
        if flag:
            cut += 1
        else:
            for i in range(group):
                if j < W - 1:
                    tmp[i][j + 1] += tmp[i][j]
    return cut


for i in range(2 ** (H - 1)): #ビットでカットするラインを探索
    lst = [0] * H
    for j in range(H - 1):
        if (i >> j) & 1: #切れるとき
            lst[j] = 1
    # print (lst)
    ans = min(ans, calc(lst))

print (ans)
    


### FIXED CODE ###

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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

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

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):
    break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (dp[nx][ny] >= (dp[p[0]][p[1]] + 1)):
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)


### FIXED CODE ###

#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)
### BUGGY CODE ###

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

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0
for i in range(1, N+1):
    for k in range(1, K+1):
        if i + k <= N:
            dp[i+k] = min(dp[i + k], dp[i] + abs(h_list[i-1] - h_list[i-1+k]))

print(dp[N])


### FIXED CODE ###

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

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0
for i in range(1, N+1):
    for k in range(1, K+1):
        if i + k <= N:
            dp[i+k] = min(dp[i + k], dp[i] + abs(h_list[i-1] - h_list[i-1+k]))

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

n, m = map(int,input().split())
cards = [1 for _ in range(n)]
for _ in range(m):
    l,r= map(lambda x: int(x) - 1,input().split())
    if 0 < l:    
        for i in range(l):
            cards[i] = 0
    if r < n-1:
        for i in range(r+1,n):
            cards[i] = 0
print(sum(cards))

### FIXED CODE ###

n, m = map(int,input().split())
cards = [1 for _ in range(n)]
L = 0
R = n-1
for _ in range(m):
    l,r= map(lambda x: int(x) - 1,input().split())
    L = max(L,l)
    R = min(R,r)
    
print(max(0,R-L+1))
### BUGGY CODE ###

n =int(input())

ans =[]
for i in range(10**9):
  if (i ** 0.5).is_integer() and i <= n:
    ans.append(i)
    
    
print(ans[-1])
    
    

    

### FIXED CODE ###

n = int(input())
m = 1
for i in range(1, n):
    if i ** 2 > n:
        break
    m = i ** 2
print(m)
### BUGGY CODE ###

n = int(input())
a = [int() for _ in input().split()]
cnt =0
while all(i%2==0 for i in a):
    a = [int(i//2) for i in a]
    cnt +=1
print(cnt)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
c = 0
while all(a%2 == 0 for a in A) :
    for i in range(len(A)): A[i] = A[i]/2
    c += 1
print(c)
### BUGGY CODE ###

from collections import deque

n,q = map(int,input().split())
graph = [[] for _ in range(n)]
connect = [[_] for _ in range(n)]
cnt = [0] * n

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(n):
    que = deque(graph[i])
    while que:
        c = que.popleft()
        if c > i:
            connect[i].append(c)
            for j in graph[c]:
                if j > i and j not in connect[i]:
                    que.append(j)

for i in range(q):
    p,q = map(int,input().split())
    p -= 1
    for j in connect[p]:
        cnt[j] += q

print(str(cnt).replace('[','').replace(']','').replace(',',''))


### FIXED CODE ###

from collections import deque
def main():
    n,q = map(int,input().split())
    values = [0]*n
    links = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = map(int,input().split())
        links[a-1].append(b-1)
        links[b-1].append(a-1)
    
    for _ in range(q):
        p,x = map(int,input().split())
        values[p-1] += x
    d = deque()
    d.append((0,-1))
    
    while len(d) != 0:
        i,p = d.popleft()
        for j in links[i]:
            if j==p:
                continue
            values[j] += values[i]
            d.append((j,i))
    print(*values)
    
main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
print(len(result))


### FIXED CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))
### BUGGY CODE ###

LOCAL = True   and False


def dprint(*args):
  if LOCAL:
    print(*args)


n = int(input())
a = []
xy = []
# x = []
# y = []
for _ in range(n):
  a.append(int(input()))
  # for _ in range(a[-1]):
  # xy = list(map(int, input().split()))
  # x[i].append(xy[0])
  # y[i].append(xy[1])
  xy.append([list(map(int, input().split())) for _ in range(a[-1])])

anses = []

for x in range(2 ** n):
  flag = True
  cnt = 0
  dprint('x', x)
  for i in range(n):
    if x & (1 << i) != 0:
      dprint('i', i)
      cnt += 1
      for j in range(a[i]):
        dprint(int(x & (1 << (xy[i][j][0] - 1)) != 0) != xy[i][j][1])
        if int(x & (1 << (xy[i][j][0] - 1)) != 0) != xy[i][j][1]:
          flag = False
  if flag:
    anses.append(cnt)

dprint(anses)
print(max(anses))


### FIXED CODE ###

LOCAL = True   and False


def dprint(*args):
  if LOCAL:
    print(*args)


n = int(input())
a = []
xy = []
# x = []
# y = []
for _ in range(n):
  a.append(int(input()))
  # for _ in range(a[-1]):
  # xy = list(map(int, input().split()))
  # x[i].append(xy[0])
  # y[i].append(xy[1])
  xy.append([list(map(int, input().split())) for _ in range(a[-1])])

anses = []

for x in range(2 ** n):
  flag = True
  cnt = 0
  dprint('x', x)
  for i in range(n):
    if x & (1 << i) != 0:
      dprint('i', i)
      cnt += 1
      for j in range(a[i]):
        dprint(int(x & (1 << (xy[i][j][0] - 1)) != 0) != xy[i][j][1])
        if int(x & (1 << (xy[i][j][0] - 1)) != 0) != xy[i][j][1]:
          flag = False
  if flag:
    anses.append(cnt)

dprint(anses)
print(max(anses))
### BUGGY CODE ###

n = int(input())
a_list = [int(i) for i in input().split()]
divide = 10 ** 9 + 7

sum = 0
for i in range(n):
    for j in range(i+1, n):
        # print(a_list[i], a_list[j] , a_list[i] ^ a_list[j])
        sum += (a_list[i] ^ a_list[j]) % divide

print(sum  % divide)

### FIXED CODE ###

n = int(input())
divide = 10 ** 9 + 7

a = [format(i, '060b') for i in map(int, input().split())]
ans = []

for i in range(60):
    bit_list = [b[59-i] for b in a]
    val = bit_list.count('0') * bit_list.count('1')
    ans.append((val * 2 ** i))

print(sum(ans)%divide)
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] = (numerator[k - offset] *pow(pivot, mod-2, mod))%mod
                denominator[k] = (denominator[k] *pow(pivot, mod-2, mod))%mod
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
            result %= mod
    return int(result)

ans = ((pow(2, n, mod)-1)%mod-nCr(n, a)-nCr(n, b))%mod
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        x %= mod
        y *= i
        y %= mod
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)
### BUGGY CODE ###

K,S=map(int,input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:ans+=1

print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        z = S-(x+y)
        if z <= K and z >= 0:ans+=1

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

N = int(input())
a = [int(i) for i in input().split()] 
b =[0]
i = 1
num = 0
while i < N+1:
    b.append(sum(a[0:i]))
    i = i+1
b.sort()
j = 0
num = 0
v = 0
while j < N:
    if b[j+1] == b[j]:
        v = v+1
    else:
        num = num + (v*(v+1))//2
        v = 0
    j = j +1
num = num + (v*(v+1))//2
print(num)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()] 
b =[0]*(N+1)
for i in range(N):
    b[i+1]= b[i] + a[i]
b.sort()
j = 0
num = 0
v = 0
while j < N:
    if b[j+1] == b[j]:
        v = v+1
    else:
        num = num + (v*(v+1))//2
        v = 0
    j = j +1
num = num + (v*(v+1))//2
print(num)
### BUGGY CODE ###

k = int(input())
ans = [str(i) for i in range(1,10)]
c = 0
while len(ans)!=k:
    now = ans[c]
    t = int(now[-1])
    if t != 0:
        ans.append(str(now) +str(t-1))

    ans.append(str(now) +str(now)[-1])

    if t != 9:
        ans.append(str(now) +str(t+1))

    c += 1
print(ans[k-1])

### FIXED CODE ###

k = int(input())
ans = [str(i) for i in range(1,10)]
c = 0

while len(ans) < k:
    now = ans[c]
    t = int(now[-1])
    if t != 0:
        ans.append(str(now) +str(t-1))

    ans.append(str(now) +str(now)[-1])

    if t != 9:
        ans.append(str(now) +str(t+1))

    c += 1
print(ans[k-1])
### BUGGY CODE ###

n, m = map(int, input().split())
for i in range(m//n,0,-1):
  if m%i == 0:
    print(i)
    break

### FIXED CODE ###

n,m = map(int, input().split())
l = []
for i in range(1,int(m**0.5)+1):
  if m%i == 0:
    l.append(i)
    l.append(m//i)
r = [x for x in l if x <= m//n]
print(max(r))
### BUGGY CODE ###

L, R = map(int, input().split())
min_mod = 2019
flg=[1]*2019
for i in range(L,R):
    flg2=[1]*2019
    idx=i%2019
    if flg[idx]==1:
        for j in range(i+1,R+1):
            mod  = (i*j)%2019
            if flg2[mod]==1:                       
                if min_mod > mod:
                    min_mod=mod
                flg2[mod]=0
            if sum(flg2)==0:
                break
        flg[idx]=0
    if sum(flg)==0:
        break
print(min_mod)

### FIXED CODE ###

L, R = map(int, input().split())
min_mod = 2019
flg=[0]*2019
flg2=[0]*2019
for i in range(L,R):
    idx=i%2019
    if flg[idx]==1:
        break
    if flg[idx]==0:
        for j in range(i+1,R+1):
            mod  = (i*j)%2019
            if flg2[mod]==1:
                break
            flg2[mod]=1
            if min_mod > mod:
                min_mod=mod
        flg[idx]=1
print(min_mod)
### BUGGY CODE ###

import sys
from collections import *
from heapq import *
from fractions import gcd
import itertools
import math
import numpy as np

sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N, K = InMap()
P = np.array(InMap())
P += 1
v = np.ones(K)
Res = np.convolve(P, v)
# Res = [sum(E[i:i+K]) for i in range(N-K+1)]
print(max(Res) / 2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N, K = InMap()
P = InMap()

Res = [0]*(N - K + 1)
tmp = sum(P[0:K])
for i in range(K, N):
    Res[i-K] = tmp
    tmp -= P[i-K]
    tmp += P[i]
Res[-1] = tmp
print((max(Res) + K) / 2)
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate
n = int(stdin.readline().rstrip())
li = [p for p in range(1,n)]
if n == 1:
    print(0)
else:
    lin = list(accumulate(li))
    print(lin[-1])

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
point = n*(n-1)//2
print(point)
### BUGGY CODE ###

n,m = map(int,input().split())
isl1 = [0]*m
isl2 = [0]*m
for i in range(m):
    (isl1[i], isl2[i]) = map(int,input().split())
    isl1[i] -= 1
    isl2[i] -= 1
boss = [-1]*n
mem = [1]*n
dpt = [0]*n
ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def sea(i, boss):
     m = 0
     while boss[i] >= 0:
          i = boss[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = isl1[i],isl2[i]
     p1,m1 = sea(i1, boss)
     p2,m2 = sea(i2, boss)
     if p1 != p2:
          if dpt[m1] < dpt[m2]:
               (p1,p2) = (p2,p1)
          boss[p2] = p1
          s -= mem[p1]*mem[p2]
          mem[p1] += mem[p2]
          mem[p2] = 0
          dpt[p1] = max(dpt[p1],dpt[p2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()
    wor = set()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor.add(x[2])
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor.remove(x[2])
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min(wor)
                flg = 0
            print(cur)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()
    wor = set()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor.add(x[2])
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor.remove(x[2])
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min(wor)
                flg = 0
            print(cur)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())

INF = 10 ** 18
dp = [[[INF] * (10*N+1) for _ in range(10*N+1)] for _ in range(N+1)]

dp[0][0][0] = 0
for i in range(N):
    a, b, c = map(int, input().split())
    for j in range(10*N+1-a):
        for k in range(10*N+1-b):
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+a][k+b] = min(dp[i+1][j+a][k+b], dp[i][j][k]+c)

ans = INF
for j in range(1, 10*N+1):
    if j * Ma > 10 * N  or j * Mb > 10 * N:
        break

    ans = min(ans, dp[N][j*Ma][j*Mb])

if ans == INF:
    ans = -1

print(ans)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())

INF = 10 ** 18
dp = [[[INF] * (10*N+1) for _ in range(10*N+1)] for _ in range(N+1)]

dp[0][0][0] = 0
for i in range(N):
    a, b, c = map(int, input().split())
    for j in range(10*N+1-a):
        for k in range(10*N+1-b):
            if dp[i][j][k] == INF:
                continue
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+a][k+b] = min(dp[i+1][j+a][k+b], dp[i][j][k]+c)

ans = INF
for j in range(1, 10*N+1):
    if j * Ma > 10 * N  or j * Mb > 10 * N:
        break

    ans = min(ans, dp[N][j*Ma][j*Mb])

if ans == INF:
    ans = -1

print(ans)