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

import sys
input = sys.stdin.readline


def read():
    N, S = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, S, A


def solve(N, S, A, MOD=998244353):
    dp = [0 for j in range(S+1)]
    dp[0] = 1
    for i in range(N):
        for j in range(S, -1, -1):
            v = 2 * dp[j]
            if j - A[i] >= 0:
                v += dp[j-A[i]]
            dp[j] = v % MOD
    return dp[S]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N, S = map(int, input().strip().split())
    A = np.fromstring(input().strip(), dtype=np.int32, sep=" ")
    return N, S, A


@njit
def solve(N, S, A, MOD=998244353):
    dp = np.zeros((S+1), dtype=np.int32)
    dp[0] = 1
    for i in range(N):
        for j in range(S, -1, -1):
            v = 2 * dp[j]
            if j - A[i] >= 0:
                v += dp[j-A[i]]
            dp[j] = v % MOD
    return dp[S]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

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

P=[]
Y=[]
for i in range(M):
	P_tmp,Y_tmp = map(int, raw_input().split())
	P.append(P_tmp)
	Y.append(Y_tmp)

S={}

for i in Y:
	key = str(P[Y.index(i)]) + "_"
	try:
		S[key]
	except:
		S[key]=[]
	S[key].append(i)

for i in S.keys():
	S[i]=sorted(S[i])

for i in Y:
	key = str(P[Y.index(i)]) + "_"
	print "{0:06d}".format(P[Y.index(i)]) + "{0:06d}".format(S[key].index(i)+1)

### FIXED CODE ###

from collections import defaultdict as dd
 
d=dd(int)
n,m=map(int,input().split())
l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]
 
o=sorted(l,key=lambda x:x[2])
for i,j in enumerate(o):
  d[j[1]]+=1
  o[i][3]=d[j[1]]
 
for i in sorted(o):
  print('{0:06d}'.format(i[1])+'{0:06d}'.format(i[3]))
### BUGGY CODE ###

n = int(input())
data = list(map(int,input().split()))
data = sorted(data, reverse=True)
sum = 0
while data != []:
    del data[0]
    del data[-1]
    sum += data[0]
    del data[0]
print(sum)

### FIXED CODE ###

n = int(input())
data = list(map(int,input().split()))
data = sorted(data, reverse=True)
sum = 0
for i in range(n):
    sum += data[1+2*i]
print(sum)
### BUGGY CODE ###

from bisect import bisect_left, bisect

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A = sorted(A,reverse = False)
C = sorted(C,reverse = False)

cnt = 0
for i in B:
    #print( A[:bisect_left(A,i)],C[bisect(C,i):])
    cnt += len(A[:bisect_left(A,i)]) *len(C[bisect(C,i):])
    
print(cnt)  

### FIXED CODE ###

from bisect import bisect_left, bisect

n=int(input())
la=sorted(list(map(int,input().split())))
lb=list(map(int,input().split()))
lc=sorted(list(map(int,input().split())))
ans=0
for i in lb:
    ans+=bisect_left(la,i)*(len(lc)-bisect(lc,i)) #iの挿入点つまりiより小さい値の数×(Cの総数-
print(ans)
### BUGGY CODE ###

a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

### FIXED CODE ###

from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))
### BUGGY CODE ###

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

    for _ in range(q):
        tmp = input()
        if len(tmp) == 1:
            s = s[::-1]
        else:
            if tmp[2] == '1':
                s = tmp[4] + s
            else:
                s = s + tmp[4]
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

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

import re

s = S = input()
while '01' in s or '10' in s:
    s = s.replace('01', '').replace('10', '')
print(len(S) - len(s))


### FIXED CODE ###

S = input()

xs = [S[0]]
for c in S[1:]:
    if xs and xs[-1] != c:
        xs.pop()
    else:
        xs.append(c)
print(len(S) - len(xs))
### BUGGY CODE ###

inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
S = set()
for i in range(N):
    S.add((A[i],i))
for _ in range(M):
    m = max(S)
    S.remove(m)
    S.add((m[0]//2, m[1]))
ans = sum(v for v, i in S)
print(ans)

### FIXED CODE ###

import heapq
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
q = []
for a in A:
    heapq.heappush(q,-a)
for _ in range(M):
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q,-a)
print(-sum(q))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
H, W = [int(x) for x in input().split()]
board = []
for _ in range(H):
    board.append(input())

L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if board[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

for i in range(H):
    for j in reversed(range(W)):
        if board[i][j] == '.':
            if j == W - 1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

for j in range(W):
    for i in range(H):
        if board[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1

for j in range(W):
    for i in reversed(range(H)):
        if board[i][j] == '.':
            if i == H - 1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1

ans = 0
for i in range(H):
    for j in range(W):
        cand = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, cand)
        
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
H, W = [int(x) for x in input().split()]
board = []
for _ in range(H):
    board.append(input())

L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if board[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

for i in range(H):
    for j in reversed(range(W)):
        if board[i][j] == '.':
            if j == W - 1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

for j in range(W):
    for i in range(H):
        if board[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1

for j in range(W):
    for i in reversed(range(H)):
        if board[i][j] == '.':
            if i == H - 1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1

ans = 0
for i in range(H):
    for j in range(W):
        cand = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, cand)
        
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
query = []
for i in range(m):
    qList = list(map(int, input().split()))
    query.append(qList)
result = [[] for i in range(n)]
 
for city in query:
    result[city[0]-1].append(city[1])
 
for i in range(n):
    result[i].sort()
 
for city in query:
    rank = result[city[0]-1].index(city[1])+1
    prefStr = "0"*(6-len(str(city[0]))) + str(city[0])
    rankStr = "0"*(6-len(str(rank))) + str(rank)
    resultStr = "{}{}".format(prefStr, rankStr)
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

def resolve():
    N = int(input())
    A_list = list(map(int,input().split()))

    #answer_list = [0] * len(A_list)
    answer_list = []

    for i in range(len(A_list)):
        answer_list.append(A_list.index(i+1)+1)

    for a in answer_list:
        print(a, end=' ')

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
ans = [0] * N
for i in range(len(A)):
    ans[A[i]-1] = i + 1
 
for a in ans:
    print(a, end=' ')
### BUGGY CODE ###

N = int(input())
AList = list(map(int, input().split()))

count = 0
roop = 0
while True:
	for i in range(N):
		if AList[i] % 2 == 0:
			AList[i] = AList[i] / 2
		else:
			break
		count += 1
	if count % N == 0:
		roop += 1
	else:
		break
print(roop)

### FIXED CODE ###

N = int(input())
Alist = list(map(int, input().split()))

flag = True
count = 0
while flag:
	for i in range(N):
		if Alist[i] % 2 != 0:
			flag = False
			break

	if flag:
		for i in range(N):
			Alist[i] = Alist[i] / 2
		count += 1

print(count)
### BUGGY CODE ###

import math

N=int(input())
ARRAY=[[[-1] * (N+1) for i in range(N+1)] for j in range(N+1)]

for i in range(1,N+1):
    count=0
    for x in range(1,int(math.sqrt(i))+1):
        for y in range(1,int(math.sqrt(i-x))+1):
            for z in range(1,int(math.sqrt(i-x-y))+1):

                if ARRAY[x][y][z]==-1:
                    res=x**2+y**2+z**2+x*y+y*z+z*x
                    ARRAY[x][y][z]=res
                    if res==i:
                        count+=1
                else:
                    res=ARRAY[x][y][z]
                    if res==i:
                        count+=1

    print(count)

### FIXED CODE ###

import math

N=int(input())
ARR=[0]*(N+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            res=x**2+y**2+z**2+x*y+y*z+z*x
            if res<=N:
                ARR[res]+=1

for i in ARR[1:]:
    print(i)
### BUGGY CODE ###

n=int(input())
s=input()
r=[]
g=[]
b=[]

for i in range(len(s)):
    if s[i]=='R':
        r.append(i)
    elif s[i]=='G':
        g.append(i)
    elif s[i]=='B':
        b.append(i)

def cal(l1,l2,l3):
    cnt=0
    for _l1 in range(len(l1)):
        for _l2 in range(len(l2)):
            if l1[_l1]<l2[_l2]:
                for _l3 in range(len(l3)):
                    if l2[_l2]<l3[_l3] and l3[_l3]-l2[_l2]!=l2[_l2]-l1[_l1]:
                        cnt+=1
    return cnt
        
count=0
count+=cal(r,g,b)
count+=cal(r,b,g)
count+=cal(g,r,b)
count+=cal(g,b,r)
count+=cal(b,r,g)
count+=cal(b,g,r)
print(count)



### FIXED CODE ###

n=int(input())
s=input()
c=s.count
m=c('R')*c('G')*c('B')
for i in range(n):
  for j in range(i+2,n,2):
    if s[i]!=s[i+j>>1]!=s[j]!=s[i]:
      m-=1
print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    idEle = -INF  # max
    def _binOpe(x, y):
        return x if x >= y else y  # max
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A  # set
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, K = map(int, input().split())
    As = [int(input()) for _ in range(N)]

    maxA = max(As)

    data, numPow2 = makeSegTree(maxA+1)
    setInit([0]*(maxA+1))

    for A in As:
        L, R = A-K, A+K
        if L < 0:
            L = 0
        if R > maxA:
            R = maxA
        v = getValue(L, R+1)
        update(A, v+1)

    ans = getValue(0, maxA+1)
    print(ans)


solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    idEle = -INF  # max
    def _binOpe(x, y):
        return x if x >= y else y  # max
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A  # set
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, K = map(int, input().split())
    As = [int(input()) for _ in range(N)]

    maxA = max(As)

    data, numPow2 = makeSegTree(maxA+1)
    setInit([0]*(maxA+1))

    for A in As:
        L, R = A-K, A+K
        if L < 0:
            L = 0
        if R > maxA:
            R = maxA
        v = getValue(L, R+1)
        update(A, v+1)

    ans = getValue(0, maxA+1)
    print(ans)


solve()
### BUGGY CODE ###

import itertools
N = int(input())
h_list = list(map(int, input().split()))
c_list = list(itertools.combinations(range(N),2))
ans = 0

for c in c_list:
        if abs(c[0] - c[1]) == h_list[c[0]] + h_list[c[1]]:
            ans += 1

print(ans)

### FIXED CODE ###

input()
A = [int(h) for h in input().split()]
iph_dic = {}
pair_of_spies = 0

for i, h in enumerate(A):
    if i - h in iph_dic:
        pair_of_spies += iph_dic[i - h]
    if i + h in iph_dic:
        iph_dic[i + h] += 1
    else:
        iph_dic[i + h] = 1

print(pair_of_spies)
### BUGGY CODE ###

from collections import defaultdict
import os, sys
def debug(*args): print(*args, file=sys.stderr)# os.environ.get("USER")
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#print(dd)
B=sorted(A,reverse=True)
ans=0
for x in B:
    debug(A)
    #print(x)
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            #print(ans)
            #print(dd)
    else:
        s+=1
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        # if used[mid]:
        #     res = bisect(val, mid+1, end)
        #     if res is not None:
        #         return res
        #     res = bisect(val, start, mid)
        #     return res
        # else:
        #     used[mid] = True
        #     debug("fuga", used)
        #     return mid
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i]  == val):
    #         used[i] = True
    #         return i
    return None


def _find(b, end, e):
    "slow!!!!"
    # debug(b, end, e)
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    # for i in reversed(range(end)):
    #     if (not used[i]) and (a[i] + b == 2**e):
    #         used[i] = True
    #         return i
    # return None


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 1


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

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'

    index_sets = [set() for _ in range(26)]
    pointers = []

    longest = 0
    for i in range(len(s)):
        c = s[i]
        order = ord(c) - ord('a')
        index_set = index_sets[order]
        next_pointers = []
        for _ in range(len(pointers)):
            cur, length, origin = pointers.pop()
            if s[cur+1] == c and cur+1 != origin:
                next_pointers.append([cur+1, length+1, origin])
                longest = max(longest, length+1)
        pointers = next_pointers

        for index in index_set:
            longest = max(longest, 1)
            pointers.append([index, 1, i])
        index_sets[order].add(i)

    print(longest)


main()


### FIXED CODE ###


import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    res = 0
    for i in range(n-1, -1, -1):
        for j in range(n-1, i, -1):
            if s[i] == s[j]:
                if j == n-1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i+1][j+1]+1
                res = max(res, min(dp[i][j], j-i))
    print(res)


main()
### BUGGY CODE ###

s = input()
change_flag = 1
for i in range(int(input())):
    a = input().split(" ")
    if(a[0] == "1"):
        change_flag *= -1
    else:
        if((a[1] == "1" and change_flag == 1) or (a[1] == "2" and change_flag == -1)):
            s = a[2] + s
        else:
            s = s + a[2]

if(change_flag == -1):
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
b = ""
f = ""
change_flag = 1
for i in range(int(input())):
    a = input().split(" ")
    if(a[0] == "1"):
        change_flag *= -1
    else:
        if((a[1] == "1" and change_flag == 1) or (a[1] == "2" and change_flag == -1)):
            b = a[2] + b
        else:
            f = f + a[2]

if(change_flag == -1):
    print(f[::-1]+s[::-1]+b[::-1])
else:
    print(b+s+f)
### BUGGY CODE ###

N,M,K=map(int,input().split())
table=[]
for i in range(N):
    a,b,c=map(int,input().split())
    table.append([a,b,c])

inf=10**9
#[N+1][400a][400b]
dp=[[[inf]*401 for i in range(401)]for i in range(N+1)]
dp[0][0][0]=0
for i in range(1,N+1):
    a,b,c = table[i-1]
    for j in range(401):
        for k in range(401):
            dp[i][j][k]=dp[i-1][j][k]
            if 400>=j-a>=0 and 400>=k-b>=0:
                dp[i][j][k] =min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)

ans =10**9
i=1
while max(M,K)*i <401:
    ans = min(ans,dp[N][M*i][K*i])
    i=i+1
if ans ==10**9:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N,M,K=map(int,input().split())
table=[]
for i in range(N):
    a,b,c=map(int,input().split())
    table.append([a,b,c])

inf=10**9
#[N+1][400a][400b]
dp=[[[inf]*401 for i in range(401)]for i in range(N+1)]
dp[0][0][0]=0
for i in range(1,N+1):
    a,b,c = table[i-1]
    for j in range(401):
        for k in range(401):
            dp[i][j][k]=dp[i-1][j][k]
            if 400>=j-a>=0 and 400>=k-b>=0:
                dp[i][j][k] =min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)

ans =10**9
i=1
while max(M,K)*i <401:
    ans = min(ans,dp[N][M*i][K*i])
    i=i+1
if ans ==10**9:
    print(-1)
else:
    print(ans)