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

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    s = input()
    dp1 = [INF] * (n + 1)
    dp1[0] = 0

    for i in range(n):
        for j in range(1, m + 1):
            if i + j > n:
                break
            if s[i + j] == "0":
                dp1[i + j] = min(dp1[i + j], dp1[i] + 1)

    dp2 = [-INF] * (n + 1)
    dp2[0] = dp1[n]
    t = s[::-1]

    for i in range(n):
        for j in range(1, m + 1):
            if i + j > n:
                break
            if t[i + j] == "0":
                dp2[i + j] = max(dp2[i + j], dp2[i] - 1)
    dp2 = dp2[::-1]
    if dp1[n] != INF:
        res = []
        i = 0
        p = 0
        cnt = 0
        while i < n:
            i += 1
            if dp2[i] == cnt + 1:
                res.append(i-p)
                p = i
                cnt += 1
        print(*res)
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    s = input()
    t = [0] * (n + 1)

    cur = n
    for i in range(n, -1, -1):
        if s[i] == "0":
            cur = i
            t[i] = cur
        else:
            t[i] = cur

    res = []

    i = n
    while i > 0:
        nx = max(0, i - m)
        if t[nx] == i:
            return print(-1)
        else:
            res.append(i - t[nx])
            i = t[nx]

    print(*res[::-1])


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

n = int(input())
a = list(map(int, input().split()))
m = 0
for i in range(n):
  m += a[i]*(sum(a[i+1:])%(10**9+7))
  m = m%(10**9+7)
print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sum([(i**2) for i in a])
print(((sum(a)**2-b)//2)%(10**9+7))
### BUGGY CODE ###


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

N = int(input())
S = [int(input()) for _ in range(N)]

ans = 0
for i in range(2 ** N):
    box = []
    for j in range(N):
        if ((i >>  j) & 1):
            box.append(S[j])

    x = sum(box)
    if x % 10 == 0:
        x = 0
    ans = max(ans, x)

#    print(box)

print(ans)

### FIXED CODE ###



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

def calc_sum(s):
    if s % 10 == 0:
        return 0
    else:
        return s

N = int(input())
S = [int(input()) for _ in range(N)]

ans = calc_sum(sum(S))
if ans > 0:
    print(ans)
    exit()

ans = 0
for i in range(N):
    s = S[0:i] + S[i+1:]
    ans = max(ans, calc_sum(sum(s)))

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

import fractions
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7

lcm=A[0]
for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//fractions.gcd(lcm,A[i])

ans=0
for i in range(n):
  ans=(ans+lcm//A[i])%mod
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]

chk=True

for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//gcd(lcm,A[i])
  if lcm>10**50000:
    chk=False
    break

if chk:
  ans=0
  for i in range(n):
    ans=(ans+lcm//A[i])%mod
  print(ans)
else:
  ans=0
  mult=1
  for a in A:
    mult=(mult*a)%mod
  for a in A:
    ans=(ans+mult*pow(a,mod-2,mod))%mod
  print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    for i in range(n):
        for j in range(i+1):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
    ans = 0
    for i in range(n):
        for j in range(i+1):
            tmp = min(dp[i][j], i-j)
            ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

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

n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]

inds = [[] for _ in range(max(a)+1)]
y = [0]*n

for i in range(n):
    if inds[a[i]]:
        y[inds[a[i]][-1]] = i+1 - inds[a[i]][-1]
    inds[a[i]].append(i)

for j in range(max(a)+1):
    if inds[j]:
        y[inds[j][-1]] = n+inds[j][0]+1 - inds[j][-1]

length = (n*k*2).bit_length()

db = [y]
for m in range(length):
    next_y = [0]*n
    for i in range(n):
        next_y[i] = db[-1][i] + db[-1][(i+db[-1][i]) % n]
    db.append(next_y)


def last():
    cur = 0
    while True:
        for i in range(length+1):
            if cur + db[i][cur % n] > n*k:
                if i != 0:
                    cur += db[i-1][cur % n]
                    break
                else:
                    return cur


cur = last()

ans = []
while cur < n*k:
    if cur + db[0][cur % n] > n*k:
        ans.append(cur)
        cur += 1
    elif cur + db[0][cur % n] == n*k:
        break
    else:
        cur = cur + db[0][cur % n]

print(*map(lambda x: a[x % n]+1, ans))


### FIXED CODE ###

from bisect import bisect_right
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

d = {}
for i in range(n):
    if a[i] in d:
        d[a[i]].append(i)
    else:
        d[a[i]] = [i]


def simulate(k):
    if k == 0:
        return 0, []
    lap = 1
    res = [0]
    while True:
        s = res.pop()
        nxt = d[a[s]][bisect_right(d[a[s]], s) % len(d[a[s]])] + 1
        if nxt == n:
            if lap == k and s == n-1:
                res.append(s)
            if s == n-1:
                lap += 1
            return lap, res
        elif nxt <= s+1:
            if lap == k:
                res.append(s)
                if s == n-1:
                    return lap, res
                res.append(s+1)
                if s+1 == n-1:
                    return lap, res
            else:
                res.append(nxt)
                lap += 1
        else:  # s+1 < nxt
            s = nxt
            res.append(s)
    return 0


period, ans = simulate(k)

if period != k:
    lap, ans = simulate(k % period)

print(*[a[x] for x in ans])
### BUGGY CODE ###

n = int(input())

# alp = ["a","b","c","d","e",
# "f","g","h","i","j",
# "k","l","m","n","o",
# "p","q","r","s","t",
# "u","v","w","x","y","z"]
# 
ans = 0
# array1 = np.zeros().reshape( n,10)


# list1 = []
list_s = []

for i in range(n):
    s = input()
    list_s.append(s)

list_s = list(map(sorted, list_s))

ans = sum(map(lambda y: (sum(map(lambda x: x==list_s[y],list_s)) -1),list(range(n))))
# for i in range(n):
#     ans = ans + sum(map(lambda x: x==list_s[i],list_s)) -1

print(int(ans/2))

### FIXED CODE ###

n = int(input())

ans = 0
ans_dict = {}

for i in range(n):
    s = input()
    s = ''.join(sorted(s))
    if(s in ans_dict):
        ans += ans_dict[s]
        ans_dict[s] += 1
    else:
        ans_dict[s] = 1
        
print(int(ans))
### BUGGY CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))

totals=[]
for i in range(N-K+1):
    j=i+K
    total = sum(Dices[i:j])
    totals.append(total)

print(max(totals))



### FIXED CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))
import numpy as np 
Dices = np.cumsum(Dices)
# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=np.append(0,Dices)
total = 0
# for i in range(N+1):
#     S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])

print(total)
### BUGGY CODE ###

def solve(N, M, fridens):
    groups = {}
    for x in range(N):
        groups[x] = [x]

    for A, B in friends:
        if B in groups:
            groups[A].append(B)
            del groups[B]

    ans = len(max(groups.values(), key=len))
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    friends = []
    for _ in range(M):
        AB = sorted([x - 1 for x in map(int, input().split())])
        if AB not in friends:
            friends.append(AB)
    solve(N, M, friends)


### FIXED CODE ###

n, m = map(int, input().split())
par = list(range(n))


def find(x):
    while par[x] != x:
        par[x] = par[par[x]]
        x = par[x]
    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 1)]

for k in range(n):
    s[find(k)] += 1


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

import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 0
def dfs(node):
    todo = set()
    for nextnode in graph[node]:
        if nextnode not in seen:
            seen.add(nextnode)
            todo.add(nextnode)
    for nextnode in todo:
        dfs(nextnode)
done = set()
while len(done) < n:
    seen = set()
    for i in range(1,n+1):
        if i not in done:
            break
    dfs(i)
    ans = max(ans,len(seen))
    done |= seen
print(ans)

### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 1

def dfs(node):
    while len(todo) > 0:
        node = todo.pop()
        if tf[node] == 0:
            tf[node] = 1
            seen.add(node)
            for nextnode in graph[node]:
                todo.append(nextnode)

todo = deque()
done = set()
tf = [0 for _ in range(n+1)]
for i in range(1,n+1):
    if i in done:
        continue
    else:
        todo.append(i)
        seen = set()
        dfs(i)
        #print(i,seen)
        ans = max(ans,len(seen))
        done |= seen
print(ans)
### BUGGY CODE ###

def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= 1000000007
        b *= i + 1
        b %= 1000000007
    return a * pow(b, 1000000005, 1000000007) % 1000000007


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

A.sort(reverse = True)
result = 0
for i in range(N - K + 1):
    result += A[i] * mcomb(N - (i + 1), K - 1)
    result %= 1000000007

A.sort()
t = 0
for i in range(N - K + 1):
    t += A[i] * mcomb(N - (i + 1), K - 1)
    t %= 1000000007

result -= t
result += 1000000007
result %= 1000000007
print(result)


### FIXED CODE ###

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

fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % 1000000007


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007


A.sort(reverse = True)
result = 0
for i in range(N - K + 1):
    result += A[i] * mcomb(N - (i + 1), K - 1)
    result %= 1000000007

A.sort()
t = 0
for i in range(N - K + 1):
    t += A[i] * mcomb(N - (i + 1), K - 1)
    t %= 1000000007

result -= t
result += 1000000007
result %= 1000000007
print(result)
### BUGGY CODE ###

N = int(input(""))
M = []

for i in range(N):
    p = input("")
    if p not in M:
        M.append(p)

print(len(M))



### FIXED CODE ###

N = int(input(""))
M = []
n = 0

for i in range(N):
    p = input("")
    M.append(p)

Mm = list(set(M))

print(len(Mm))
### BUGGY CODE ###

N = int(input())
S = input()

dic = {'R':0, 'G':0, 'B':0}
for i in range(N):
  dic[S[i]] += 1

ans = dic['R'] * dic['G'] * dic['B']

for i in range(N):
  for j in range(i+1, N):
    if 2*j - i < len(S):
      if S[i] == 'R' and S[j] == 'G' and S[2*j - i] == 'B':
        ans -= 1

      if S[i] == 'R' and S[j] == 'B' and S[2*j - i] == 'G':
        ans -= 1

      if S[i] == 'G' and S[j] == 'R' and S[2*j - i] == 'B':
        ans -= 1

      if S[i] == 'G' and S[j] == 'B' and S[2*j - i] == 'R':
        ans -= 1
      
      if S[i] == 'B' and S[j] == 'G' and S[2*j - i] == 'R':
        ans -= 1

      if S[i] == 'B' and S[j] == 'R' and S[2*j - i] == 'G':
        ans -= 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

dic = {'R':0, 'G':0, 'B':0}
for i in range(N):
  dic[S[i]] += 1

ans = dic['R'] * dic['G'] * dic['B']

for i in range(N):
  for j in range(i+1, N):
    if 2*j - i < len(S):
      if S[i] == 'R' and S[j] == 'G' and S[2*j - i] == 'B':
        ans -= 1

      if S[i] == 'R' and S[j] == 'B' and S[2*j - i] == 'G':
        ans -= 1

      if S[i] == 'G' and S[j] == 'R' and S[2*j - i] == 'B':
        ans -= 1

      if S[i] == 'G' and S[j] == 'B' and S[2*j - i] == 'R':
        ans -= 1
      
      if S[i] == 'B' and S[j] == 'G' and S[2*j - i] == 'R':
        ans -= 1

      if S[i] == 'B' and S[j] == 'R' and S[2*j - i] == 'G':
        ans -= 1

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

inf = input().split()
H = int(inf[0])
W = int(inf[1])
sheet = [[] for i in range(H+2)]
score = [[] for i in range(H+2)]
m = 0
 
for h in range(H+2):
  if h==0 or h==H+1:
    a = [False]*(W+2)
    b = [(0,0)]*(W+2)
    sheet[h]=a
    score[h]=b
  else:
    line = input()
    a = []
    b = []
    a += [False]
    b += [(0,0)]
    for w in range(W):
      b+=[(0,0)]
      if line[w]=='.':
        a += [True]
      else:
        a += [False]
    a += [False]
    b += [(0,0)]
    sheet[h]=a
    score[h]=b
      
for h in range(1,H+1):
  for w in range(1,W+1):
    if sheet[h][w]:
      s = 0
      hs = 0
      ws = 0
      if sheet[h-1][w]:
        hs += score[h-1][w][0]
      else:
        i = h+1
        while sheet[i][w]:
          hs+=1
          i+=1
      if sheet[h][w-1]:
        ws += score[h][w-1][1]
      else:
        j = w+1
        while sheet[h][j]:
          ws+=1
          j+=1
      s = 1 + hs + ws
      score[h][w]=(hs, ws)
      if m < s:
        m = s
print(m)


### FIXED CODE ###

inf = input().split()
H = int(inf[0])
W = int(inf[1])
sheet = [[] for i in range(H+2)]
score = [[] for i in range(H+2)]
m = 0
 
for h in range(H+2):
  if h==0 or h==H+1:
    a = [False]*(W+2)
    b = [(0,0)]*(W+2)
    sheet[h]=a
    score[h]=b
  else:
    line = input()
    a = []
    b = []
    a += [False]
    b += [(0,0)]
    for w in range(W):
      b+=[(0,0)]
      if line[w]=='.':
        a += [True]
      else:
        a += [False]
    a += [False]
    b += [(0,0)]
    sheet[h]=a
    score[h]=b
      
for h in range(1,H+1):
  for w in range(1,W+1):
    if sheet[h][w]:
      s = 0
      hs = 0
      ws = 0
      if sheet[h-1][w]:
        hs += score[h-1][w][0]
      else:
        i = h+1
        while sheet[i][w]:
          hs+=1
          i+=1
      if sheet[h][w-1]:
        ws += score[h][w-1][1]
      else:
        j = w+1
        while sheet[h][j]:
          ws+=1
          j+=1
      s = 1 + hs + ws
      score[h][w]=(hs, ws)
      if m < s:
        m = s
print(m)
### BUGGY CODE ###

def bogosort(l):
  import random
  while 1:
    random.shuffle(l)
    for i in range(1,len(l)):
      if l[i]<l[i-1]:
        break
    else:
      return l
i=lambda:list(map(int,input().split()))
n,m,x,y=i()
a=bogosort(i()+[x])
b=bogosort(i()+[y])
if a[-1]<b[0]:
    print('No War')
else:
    print('War')


### FIXED CODE ###

x,y=input().split()[2:];print('No '*(max(map(int,input().split()+[x]))<min(map(int,input().split()+[y])))+'War')
### BUGGY CODE ###

from collections import defaultdict
s = input()
k = int(input())
dd = defaultdict(lambda:0)
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    dd[s[i]] = 1
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        dd[s[i:j+1]] = 1
li = []
for key in dd:
    li.append(key)
li.sort()
print(li[k-1])

### FIXED CODE ###

from collections import defaultdict
s = input()
k = int(input())
dd = {}
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    dd[s[i]] = 1
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        if j-i+1 <= k:
            dd[s[i:j+1]] = 1
li = []
for key in dd:
    li.append(key)
li.sort()
print(li[k-1])
### BUGGY CODE ###

"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

k = int(input())
s = input()

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

ans = 0
#for i in range(k+1):
#    ans = (ans+nCr(n+k, i)*pow(25, i, mod)) % mod
#print(ans)

for i in range(k+1):
    now = pow(26, k-i, mod) * pow(25, i, mod) * nCr(i+n-1, n-1)
    ans = (ans+now) % mod
print(ans)

### FIXED CODE ###

"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

k = int(input())
s = input()

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

ans = 0
#for i in range(k+1):
#    ans = (ans+nCr(n+k, i)*pow(25, i, mod)) % mod
#print(ans)

for i in range(k+1):
    now = pow(26, k-i, mod) * pow(25, i, mod) * nCr(i+n-1, n-1)
    ans = (ans+now) % mod
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
stat = 0
a = 0
bc = 0
abc = 0
ans = 0
def count():
    global ans, a, bc, abc
    newa = a+abc
    cnt = abc
    while cnt>0:
        ans += cnt
        cnt -= 1
        if a>0:
            a -= 1
            cnt += 1
        if bc>0:
            bc -= 1
            cnt += 1
    a = newa
    bc = 0
    abc = 0
i = 0
while i<n:
    if stat==0:
        if s[i:i+3]=='ABC':
            a = 0
            abc = 1
            stat = 2
            i += 3
        elif s[i]=='A':
            a = 1
            stat = 1
            i += 1
        else:
            i += 1
    elif stat==1:
        if s[i:i+3]=='ABC':
            abc = 1
            stat = 2
            i += 3
        elif s[i]=='A':
            a += 1
            i += 1
        else:
            stat = 0
    elif stat==2:
        if s[i:i+3]=='ABC':
            abc += 1
            i += 3
        elif s[i:i+2]=='BC':
            bc = 1
            stat = 3
            i += 2
        else:
            count()
            stat = 1
    else:
        if s[i:i+2]=='BC':
            bc += 1
            i += 2
        else:
            count()
            stat = 1
if stat>=2:
    count()
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
stat = 0
a = 0
bc = 0
abc = 0
ans = 0
def count():
    global ans, a, bc, abc
    newa = a+abc
    cnt = abc
    while cnt>0:
        ans += cnt
        cnt -= 1
        if a>0:
            a -= 1
            cnt += 1
        if bc>0:
            bc -= 1
            cnt += 1
    a = newa
    bc = 0
    abc = 0
i = 0
while i<n:
    if stat==0:
        if s[i:i+3]=='ABC':
            a = 0
            abc = 1
            stat = 2
            i += 3
        elif s[i]=='A':
            a = 1
            stat = 1
            i += 1
        else:
            i += 1
    elif stat==1:
        if s[i:i+3]=='ABC':
            abc = 1
            stat = 2
            i += 3
        elif s[i]=='A':
            a += 1
            i += 1
        else:
            stat = 0
    elif stat==2:
        if s[i:i+3]=='ABC':
            abc += 1
            i += 3
        elif s[i:i+2]=='BC':
            bc = 1
            stat = 3
            i += 2
        else:
            count()
            stat = 1
    else:
        if s[i:i+2]=='BC':
            bc += 1
            i += 2
        else:
            count()
            stat = 1
if stat>=2:
    count()
print(ans)
### BUGGY CODE ###

a,b,n=map(int,input().split())
List=[]

def floor(m):
    return int(m)

for x in range(n+1):
    c= floor(a*x/b) - a*floor(x/b)
    List.append(c)

print(max(List))
    

### FIXED CODE ###

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

def floor(m):
    return int(m)

if n>=b:
    x=b-1
    c= floor(a*x/b) - a*floor(x/b)
else:
    x=n
    c= floor(a*x/b) - a*floor(x/b)

print(c)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(N)]

inf = float('inf')
dp = [[[inf] * 401 for _ in range(401)] for _ in range(N + 1)]

dp[0][0][0] = 0

for i in range(N):
    for j in range(401):
        for k in range(401):
            if j - abc[i][0] >= 0 and k - abc[i][1] >= 0:
                dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - abc[i][0]][k - abc[i][1]] + abc[i][2])
            else:
                dp[i + 1][j][k] = dp[i][j][k]
ans = inf
for a in range(1, 401):
    if a % Ma == 0:
        b = a // Ma * Mb
        if b <= 401:
            ans = min(ans, dp[N][a][b])
if ans == inf:
    ans = -1
print(ans)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(N)]

inf = float('inf')
dp = [[[inf] * 401 for _ in range(401)] for _ in range(N + 1)]

dp[0][0][0] = 0

for i in range(N):
    for j in range(401):
        for k in range(401):
            dp[i + 1][j][k] = dp[i][j][k]
            if j - abc[i][0] >= 0 and k - abc[i][1] >= 0:
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j - abc[i][0]][k - abc[i][1]] + abc[i][2])
ans = inf
for a in range(1, 401):
    for b in range(1, 401):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans == inf:
    ans = -1
print(ans)