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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,t = LI()
    aa = sorted([LI() for _ in range(n)])
    m = max(map(lambda x: x[0], aa))
    r = [0] * (t+m+1)
    for a,b in aa:
        for i in range(t-1,-1,-1):
            if r[i+a] < r[i] + b:
                r[i+a] = r[i] + b

    return max(r)


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,t = LI()
    aa = sorted([LI() for _ in range(n)])
    m = max(map(lambda x: x[0], aa))
    r = [0] * (t+m+1)
    for a,b in aa:
        for i in range(t-1,-1,-1):
            if r[i+a] < r[i] + b:
                r[i+a] = r[i] + b

    return max(r)


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

l,r=map(int,input().split())
a=[]
for i in range(l,r):
  for j in range(i+1,r+1):
    a.append((i*j)%2019)
print(min(a))



### FIXED CODE ###

##C
l,r=map(int,input().split())
c=(r-l)
d=2018
if c>=2018:
    print(0)
else:
    for i in range(l,r):
        for k in range(l+1,r+1):
            
            if (i*k)%2019<d:
                d=(i*k)%2019
    print(d)
### BUGGY CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template
A,B,C = inputlist()
K = int(input())
count = 0
while count < K:
    if A > B:
        B = 2*B
        count +=1
        continue
    if B > C:
        C = 2*C
        count +=1
        continue
    if A < B<C:
        print("Yes")
        exit()
if A < B < C:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())
k = int(input())

ans = 'No'
for i in range(k+1):
  if a < b*(2**i) < c*(2**(k-i)):
    ans = 'Yes'
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N=int(input())
    A = list(map(int, input().split()))
    ans=[0]*N
    for i in range(N):
        ans[i]=str(A.index(i+1)+1)
    print(' '.join(ans))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N=int(input())
    A = list(map(int,input().split()))
    ans=[None]*N
    i=1
    for a in A:
        ans[a-1]=str(i)
        i+=1
    print(' '.join(ans))

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

l = list(input())
amari = [0]*len(l)
mod = 2019
import math
for i in range(len(l)):
    amari[i] = int(l[i])*(10**(len(l)-1-i)) % mod
rui = [0]*len(l)
rui[len(l)-1] = amari[-1]
for i in range(len(l)-2,-1,-1):
    rui[i] = (rui[i+1] + amari [i])%mod
count = [0]*2020
for i in range(len(l)):
    count[rui[i]] += 1
ans = 0
for i in range(1,2020):
    if count[i] == 0 or count[i] == 1:
        continue
    ans += math.factorial(count[i]) // (math.factorial(count[i]-2)*2)
ans += count[0]
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
P = 2019
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1
print(ans)
### BUGGY CODE ###

def g(x,n):
    y = n // x
    s = int(y * (y+1) * x / 2)
    return s

n = int(input())

answer = 0
for i in range(1,n+1):
    answer += int(g(i,n))

print(answer)

### FIXED CODE ###

def g(x,n):
    y = n // x
    s = int(y * (y+1) * x / 2)
    return s

n = int(input())

answer = 0
for i in range(1,n+1):
    answer += int(g(i,n))

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

N=int(input())
c=input()
ans=0
#WRがなくなるまでの最小繰り返し数
#Rの左はR.右はなんでもOK（RR?）
#Wの右はW.左はなんでもOK(?WW)
"""
RRRRRR
WWWWWW
RWWWWWW
RRRRRRRW
の大よそ4パターンが存在する
全部やって小さいのでいい？
２か所の色が変わっていいことなんてあるのか？？？

WRWWRWRR
を３回操作で変更する方法
左にRを集め、右にWを集めきればいい
前から順にみていき処置をするか、全部見たうえで計算式を立てるか（多分公社）
Wが連続、Rが連続、RWならOK（カウントを戻す）
WとRの個数をカウントする
#半分より右側にあるWの個数、半分より左側にあるRの個数で、少ないほうがまず＋
#残りは塗り替える
#一番真ん中はWならOK、Rなら＋１
"""
#最小の分割店を見つける
if len(set(list(c)))==1:
    ans=0
    print(ans)
else:
    #最小の分割店を見つける
    ans=100000000000000000
    for i in range(N):
        W=c[:i].count("W")#変更すべきWの数
        R=c[i:].count("R")
        if max(R,W)<ans:
            ans=max(R,W)
    print(ans)    


### FIXED CODE ###

N=int(input())
c=input()
ans=0
if len(set(list(c)))==1:
    ans=0
    print(ans)
else:
    #最小の分割店を見つける
    ans=100000000000000000
    W=0
    R=c.count("R")
    for i in range(N):
        if c[i]=="W":
            W+=1
        elif c[i]=="R":
            R-=1
        if max(R,W)<ans:
            ans=max(R,W)
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [0.0] * n
for i in range(n):
    e[i] = (1 + p[i]) * 0.5
s = 0.0
for i in range(k, n + 1):
    s = max(s, sum(e[i - k:i]))
print(s)

### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [(1 + p[i]) * 0.5 for i in range(n)]
s = 0.0
for i in e[:k]:
    s += i
t = s
for i in range(n - k):
    t = t - e[i] + e[k + i]
    s = max(s, t)
print(s)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
n = [0] * N
for i in range(1, N+1):
    c = A.count(i)
    n[i-1] = c
for j in range(N):
    print(n[j])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
n = [0] * N
#A_2 A_3 ... A_N とA_1をのぞいて続くのでN-1となる
for i in range(N-1):
    n[A[i]-1] += 1

for j in range(N):
    print(n[j])
### BUGGY CODE ###

import sys


def main():
    N = int(input())
    P = tuple(map(int, input().split()))

    Kcost = [0] * (N * N)
    for sn in range(N * N):
        row, clm = divmod(sn, N)
        Kcost[sn] = min(row, N - row - 1, clm, N - clm - 1)

    Sitting = [1] * (N * N)
    Kcount = 0

    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            for dsn in (1, -1, N, -N):
                div, mod = divmod(qsn, N)
                if mod == 0 and dsn == -1: continue
                if mod == N - 1 and dsn == 1: continue
                if div == 0 and dsn == -N: continue
                if div == N - 1 and dsn == N: continue

                cdsn = qsn + dsn
                if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
                    Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
                    queue.append(cdsn)

    print(Kcount)


if __name__ == '__main__':
    main()

sys.exit()


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

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

data=[]
for n1 in range(N):
  data.append([])
  for n2 in range(N):
    data[n1].append(0)
    
for m in range(M):
  a,b=map(int,input().split(' '))
  data[a-1][b-1]=H[b-1]
  data[b-1][a-1]=H[a-1]
ans=0
for n in range(N):
  if H[n-1]>max(data[n-1]):
    ans+=1
print(ans)

### FIXED CODE ###

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

data=[]
for n in range(N):
  data.append(H[n]-1)
    
for m in range(M):
  a,b=map(int,input().split(' '))
  data[a-1]=max(data[a-1],H[b-1])
  data[b-1]=max(data[b-1],H[a-1])
  
ans=0
for n in range(N):
  if H[n-1]-1==data[n-1]:
    ans+=1
print(ans)
### BUGGY CODE ###

# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s = input()
q = INT()
for _ in range(q):
     temp = input()
     if(len(temp.split())==1):
         # print("here")
         s = s[::-1]
     else:
         t,f,c = temp.split()
         # print(t,f,c,_)
         if(f=="1"):
             s = c + s
         else:
             s = s + str(c)
print(s)


### FIXED CODE ###

# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s = input()
q = INT()
rev = 0
begg = []
end = []
for _ in range(q):
     temp = input()
     if(len(temp.split())==1):
         rev+=1

     else:
         t,f,c = temp.split()
         if(f=="1"):
             if(rev%2==0):
                 begg.append(c)
                 # s = c + s
             else:
                 end.append(c)
                 # s = s + c
         else:
             if(rev%2==0):
                 end.append(c)
                 # s = s + c
             else:
                 begg.append(c)
                 # s = c + s
abc = "".join(begg[::-1]) + s + "".join(end)
if(rev%2==0):
    print(abc)
else:
    print(abc[::-1])
### BUGGY CODE ###

# coding: utf-8
import sys,pprint
from fractions import Fraction
from collections import defaultdict

MOD = 1000000007
N = int(input())
params =[]
hatemasks = []
tilts = defaultdict(int)
zerozero = 0
zerodiv = 0
for i in range(N):
    (ai, bi) = map(int,input().split())
    if ai == 0 and bi == 0:
        zerozero += 1
    elif bi == 0:
        zerodiv += 1
    else:
        t = Fraction(ai,bi)
        tilts[t] += 1

# print(tilts,file=sys.stderr)

ans = 1
f1 = Fraction(0,1)
if f1 in tilts:
    ans *= 1+pow(2,tilts[f1],MOD)-1 + pow(2,zerodiv,MOD)-1
    del tilts[f1]
else:
    ans *= 1 + pow(2,zerodiv,MOD)-1
ans %= MOD

klist = list(tilts.keys())
for k in klist:
    kinv = Fraction(-1*k.denominator,k.numerator)
    if kinv in tilts:
        #print(k,kinv, file=sys.stderr)
        ans *= 1+pow(2,tilts[k],MOD) -1+pow(2,tilts[kinv],MOD)-1
        ans %= MOD
        del tilts[k]
        del tilts[kinv]
    else:
        ans *= 1+pow(2,tilts[k],MOD)-1
        ans %= MOD

print((ans + zerozero -1) % MOD)


### FIXED CODE ###

# coding: utf-8
import sys,pprint, math
from fractions import Fraction
from collections import defaultdict

MOD = 1000000007
N = int(input())
params =[]
hatemasks = []
tilts = defaultdict(lambda: [0,0])
zerozero = 0
zerodiv = 0
for i in range(N):
    (ai, bi) = map(int,input().split())
    if ai == 0 and bi == 0:
        zerozero += 1
        continue
    if (ai < 0) or (ai == 0 and bi < 0):
        ai *= -1
        bi *= -1
    g = math.gcd(ai,bi)
    ai = ai // g
    bi = bi // g
    if bi > 0:
        tilts[(ai,bi)][0] += 1
    else:
        tilts[(-bi,ai)][1] += 1
print(tilts,file=sys.stderr)

#sys.exit()
ans = 1
for(v1,v2) in tilts.values():
    ans *= 1 +pow(2,v1,MOD)-1 +pow(2,v2,MOD)-1
    ans %= MOD
ans = (ans+zerozero-1) % MOD
print(ans)
### BUGGY CODE ###

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

import collections
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = [None] * n
    for i in range(n):
        s[i] = str(input()).replace("\n", "")

    ans = [None] * n
    index = 0
    for i in s:
        count_word = dict()
        sorted_word = list()
        for j in i:
            if not j in sorted_word:
                count_word[j] = i.count(j)
                sorted_word.append(j)

        ans[index] = count_word
        index += 1

    pairs = list()
    sorted_num = list()
    for i in range(n):
        if i in sorted_num:
            continue
        for j in range(i + 1, n):
            if ans[i] == ans[j]:
                pairs.append(i)
                sorted_num.append(j)

    count = 0
    for v in collections.Counter(pairs).values():
        if v >= 2:
            count += int(v * (v - 1) / 2) + v
        else:
            count += 1

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = [None] * n
    for i in range(n):
        s[i] = str(input()).replace("\n", "")

    ans = dict()
    pairs = 0
    for i in s:
        i = ''.join(sorted(list(i)))

        if i in ans:
            pairs += ans[i]
            ans[i] += 1
            continue

        ans[i] = 1

    print(pairs)


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

from heapq import heapify, heappush, heappop 

INF = 1001001001

N, Q = map(int, input().split())
STXs = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

#S-X, T-X, X
future_block = [(S - X, T - X, X) for S, T, X in STXs]
future_block.append((INF, INF, INF)) #sentinel
heapify(future_block)

#T-X, S-X, X
current_block = [(INF, INF, INF)] #sentinel
current_min_pair = (INF, INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[2] > x:
            current_min_pair = (t_x, s_x, x)
        heappush(current_block, (t_x, s_x, x))
    
    search_min_flg = False
    while current_block[0][0] <= D:
        if current_min_pair == heappop(current_block):
            search_min_flg = True
    if search_min_flg:
        current_min_pair = min(current_block, key = lambda t: t[2])

    print(-1 if current_min_pair[2] == INF else current_min_pair[2])


### FIXED CODE ###

from heapq import heapify, heappush, heappop 

INF = 1001001001

N, Q = map(int, input().split())
STXs = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

#S-X, T-X, X
future_block = [(S - X, T - X, X) for S, T, X in STXs]
future_block.append((INF, INF, INF)) #sentinel
heapify(future_block)

#T-X, X
current_block = [(INF, INF)] #sentinel
current_min_pair = (INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[1] > x:
            current_min_pair = (t_x, x)
        heappush(current_block, (t_x, x))
    
    search_min_flg = False
    while current_block[0][0] <= D:
        if current_min_pair == heappop(current_block):
            search_min_flg = True
    if search_min_flg:
        current_min_pair = min(current_block, key = lambda t: t[1])

    print(-1 if current_min_pair[1] == INF else current_min_pair[1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = input()
q = int(input())

queries = [input().split() for i in range(q)]

for query in queries:
    if "1" == query[0]:
        s = s[::-1]
    elif "2" == query[0]:
        if "1" == query[1]:
            s = query[2] + s
        elif "2" == query[1]:
            s += query[2]

print(s)


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    s = input()
    q = int(input())

    queries = (input().split() for i in range(q))

    flg = True
    result = s
    pre = ""
    post = ""
    for query in queries:
        if "1" == query[0]:
            flg = not flg
        elif "2" == query[0]:
            if ("1" == query[1] and flg) or ("2" == query[1] and not flg):
                pre = query[2] + pre
            else:
                post += query[2]

    if flg:
        print(pre + result + post)
    else:
        print((pre + result + post)[::-1])


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

n, m = map(int,input().split())
 
l = [""] * m
ans3 = set([1,n+1])

for i in range(m):
    s,t = map(int,input().split())
    ans2 = [j for j in range(s,t+1) if s <= j <= t]
    if i == 0:
        ans3 = set(ans2)
        ans2.clear()
        if len(ans3) == 0:
            break
    else:
        ans3 = ans3 & set(ans2)
        ans2.clear()
        if len(ans3) == 0:
            break

print(len(ans3))

### FIXED CODE ###

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

left_max = -1
right_min = n+1

for i in range(m):
    s,t = map(int,input().split())
    left_max = max(left_max,s)
    right_min = min(right_min, t)
    
print(max(0, right_min - left_max +1))
### BUGGY CODE ###

n, m = map(int, input().split())
mod = 1000000007
a = [int(input()) for _ in range(m)]

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if i in a: continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mod = 1000000007
a = set(int(input()) for _ in range(m))

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if i not in a: dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)
### BUGGY CODE ###

from collections import deque
h = int(input())
stack = deque([h])
count = 0
while (len(stack) >= 1):
    hp = stack.pop()
    count += 1
    if (hp == 1):
        continue
    else:
        hp = hp//2
        stack.append(hp)
        stack.append(hp)
print(count)


### FIXED CODE ###

from collections import deque
h = int(input())
# stack = deque([h])
# count = 0
# while (len(stack) >= 1):
#     hp = stack.pop()
#     count += 1
#     if (hp == 1):
#         continue
#     else:
#         hp = hp//2
#         stack.append(hp)
#         stack.append(hp)
# print(count)
count = 0
hueru_ryo = 1
while h > 0:
    h = h//2
    count += hueru_ryo
    hueru_ryo *= 2
print(count)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
heapq.heapify(An)

for i in range(M):
    B,C = map(int,input().split(' '))
    for _ in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            heapq.heappush(An,tmp_min)
            break
        heapq.heappush(An,C)
print(sum(An))

### FIXED CODE ###

import heapq
N,M = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
heapq.heapify(An)
BC_list = []
for i in range(M):
    BC = list(map(int,input().split(' ')))
    BC_list.append(BC)
BC_list.sort(reverse=True,key=lambda x: x[1])
flag = False
decided_sum = []
for val in BC_list:
    B = val[0]
    C = val[1]
    for i in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            #heapq.heappush(An,tmp_min)
            decided_sum.append(tmp_min)
            flag = True
            break
        decided_sum.append(C)
        if len(An) == 0:
            flag = True
            break
    if flag:
        break
print(sum(decided_sum) + sum(An))
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# Ma:Mbを満たす量を全探索する
# 量を決めたときの最小予算は半分全列挙から分かる

from itertools import product

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

Z1 = list(product([0,1],repeat=N//2))
Z2 = list(product([0,1],repeat=N-N//2))

d1 = defaultdict(list)
d2 = defaultdict(list)

for z in Z1:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[i]
            val_b += b[i]
            cost += c[i]
    d1[(val_a,val_b)].append(cost)

for k in d1.keys():
    d1[k].sort()

for z in Z2:
    val_a = 0
    val_b = 0
    cost = 0
    for i,z0 in enumerate(z):
        if z0:
            val_a += a[N//2+i]
            val_b += b[N//2+i]
            cost += c[N//2+i]
    d2[(val_a,val_b)].append(cost)

for k in d2.keys():
    d2[k].sort()

vals = []
now = 1
while True:
    if max(Ma*now,Mb*now) <= 10*N:
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = float('inf')
for v in vals:
    for k in d1.keys():
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if d2[(left_a,left_b)]:
            if d1[k][0]+d2[(left_a,left_b)][0] < ans:
                ans = d1[k][0]+d2[(left_a,left_b)][0]

if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)