Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n,m,r = li()
r = list(li_())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
dists = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dists[i] = dijkstra(graph, n, i)

routes = list(permutations(r))

ans = 2**64-1
for route in routes:
    temp = 0
    for i in range(len(route)-1):
        temp += dists[route[i]][route[i+1]]
        
    ans = min(ans,temp)
    
print(ans)

Fixed submission:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
import numpy as np

n,m,r = li()
r = list(li_())
abc = []
graph = np.zeros((n,n))
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    
floyd_warshall(graph, directed=False, overwrite=True)

routes = list(permutations(r))

ans = float("inf")
for route in routes:
    cand = 0
    for i in range(len(route)-1):
        cand += graph[route[i]][route[i+1]]
        
    ans = min(ans, cand)
        
print(int(ans))
Buggy python submission (verdict: Runtime Error):
MOD = 1000000007

N = int(input())
S = []
for i in range(2):
    S.append(input())
    

# make XYline
xy = ""
for i in range(len(S[0])):
    if S[0][i] == S[1][i]:
        xy += "X"
    elif S[0][i] == S[0][i+1]:
        xy += "Y"

# proceed
if xy[0] == "X":
    ans = 3
else:
    ans = 6

if len(xy)==1:
    pass
else:
    for i in range(1,len(xy)):
        if xy[i-1] == "X" and xy[i] == "X":
            ans *= 2
        elif xy[i-1] == "X" and xy[i] == "Y":
            ans *= 2
        elif xy[i-1] == "Y" and xy[i] == "X":
            ans *= 1
        elif xy[i-1] == "Y" and xy[i] == "Y":
            ans *= 3

        ans = ans%MOD

    
print(ans)


Fixed submission:
MOD = 1000000007

N = int(input())
S = []
for i in range(2):
    S.append(input())
    

# make XYline
xy = ""
for i in range(len(S[0])):
    if S[0][i] == S[1][i]:
        xy += "X"
    elif i==len(S[0])-1:
        break
    elif S[0][i] == S[0][i+1]:
        xy += "Y"

# proceed
if xy[0] == "X":
    ans = 3
else:
    ans = 6

if len(xy)==1:
    pass
else:
    for i in range(1,len(xy)):
        if xy[i-1] == "X" and xy[i] == "X":
            ans *= 2
        elif xy[i-1] == "X" and xy[i] == "Y":
            ans *= 2
        elif xy[i-1] == "Y" and xy[i] == "X":
            ans *= 1
        elif xy[i-1] == "Y" and xy[i] == "Y":
            ans *= 3

        ans = ans%MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
#stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

odd = 0
ml2 = 0
ml4 = 0

for ai in a:
    if ai % 2:
        odd += 1
    elif ai % 4:
        ml2 = 1
    else:
        ml4 += 1

print("Yes" if (odd + ml2) <= (ml4 + 1) else "No")

Fixed submission:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

odd = 0
ml2 = 0
ml4 = 0

for ai in a:
    if ai % 2:
        odd += 1
    elif ai % 4:
        ml2 = 1
    else:
        ml4 += 1

print("Yes" if (odd + ml2) <= (ml4 + 1) else "No")
Buggy python submission (verdict: Runtime Error):
from collections import deque

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

b = deque([])

for i,ai in enumerate(a):
  if i%2 == 0:
    b.append(ai)
    
  else:
    b.appendleft(ai)
    
if n%2 == 1:
  print(*b[::-1])
else:
  print(*b)



Fixed submission:
N = int(input())
A = list(map(int, input().split()))

if N%2 == 0:
    b = A[N-1::-2] + A[0::2]
else:
    b = A[N-1::-2] + A[1::2]
    
print(*b)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

s = input()

cnt = Counter(s)

if len(cnt.keys()) == 1:
    print(0)
    
else:
    al_set = set(s)
    c = list(s)
    
    dic = {}
    for alpha in al_set:
        c_prev = [ci for ci in c]
        count = 0
        while any([ci != alpha for ci in c_prev]):
            c_new = []
            for j in range(len(c_prev) - 1):
                if c_prev[j] == alpha or c_prev[j+1] == alpha:
                    c_new.append(alpha)
                else:
                    c_new.append("0")
                    
            c_prev = c_new
            count += 1

            
        dic[alpha] = count
        
print(min(dic.values()))
            

Fixed submission:
from collections import Counter

s = input()

cnt = Counter(s)

if len(cnt.keys()) == 1:
    print(0)
    
else:
    al_set = set(s)
    c = list(s)
    
    dic = {}
    for alpha in al_set:
        c_prev = [ci for ci in c]
        count = 0
        while any([ci != alpha for ci in c_prev]):
            c_new = []
            for j in range(len(c_prev) - 1):
                if c_prev[j] == alpha or c_prev[j+1] == alpha:
                    c_new.append(alpha)
                else:
                    c_new.append("0")
                    
            c_prev = c_new
            count += 1

            
        dic[alpha] = count
        
    print(min(dic.values()))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

p_num = [0]*9

for a in A:
    p_num[a//400] += 1
    
ans = 0
for p in p_num[:-1]:
    if p:
        ans +=1
        
ans_min = ans
ans_max = ans + p_num[-1]

print(ans_min, ans_max)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

p_num = [0]*9

for a in A:
    if a<3200:
        p_num[a//400] += 1
    else:
        p_num[-1] += 1
    
ans = 0
for p in p_num[:-1]:
    if p:
        ans +=1
        
ans_min = max(ans,1) 
ans_max = ans + p_num[-1]

print(ans_min, ans_max)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

hasFinished = False

ans_cand = []
def dfs(cp, length):
    
    if length == N:
        if cp%10 != 0:
            print(cp)
            exit()
            
    else:
        dfs(cp+S[length], length+1)
        dfs(cp, length+1)
        
def ten2zero(num):
    if num%10==0:
        return 0
    else:
        return num        

def solve(N,S):
    S.sort(reverse=True)
    s_per5 = [s%10 for s in S]
    
    if sum(s_per5)==0:
        print(0)
        return
    
    else:    
        return dfs(0,0)

solve(N,S)

Fixed submission:
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

total = sum(S)

if total%10 == 0:
    
    new_S = []
    for s in S:
        if s%10==0:
            new_S.append(101)
        else:
            new_S.append(s)
    
        if sum(new_S) == 101*len(S):
            min_s = total
        else:
            min_s = min(new_S)
    
    print(total-min_s)
else:
    print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

ans_cand = []
def dfs(cp, length):
    global ans_cand
    
    if length == N:
        ans_cand.append(cp)
    else:
        dfs(cp+S[length], length+1)
        dfs(cp, length+1)
        
def ten2zero(num):
    if num%10==0:
        return 0
    else:
        return num        

dfs(0,0)
ans_cand = [ten2zero(ans) for ans in ans_cand]

ans_cand.sort(reverse=True)

print(ans_cand[0])

Fixed submission:
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

total = sum(S)

if total%10 == 0:
    
    new_S = []
    for s in S:
        if s%10==0:
            new_S.append(101)
        else:
            new_S.append(s)
    
        if sum(new_S) == 101*len(S):
            min_s = total
        else:
            min_s = min(new_S)
    
    print(total-min_s)
else:
    print(total)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def judge(k: int, h: list, a:int, b:int):
    h = [max(0, hi - k*b) for hi in h]
    cnt = 0
    for hi in h:
        cnt += -(-hi//(a-b))

    return True if cnt <= k else False

def binary_search(h, a, b):
    low = 0
    high = 10**18

    while high - low > 1:
        mid = (high+low) // 2
        if judge(mid, h, a, b):
            high = mid
        else:
            low = mid

    return high

n, a, b = li()
h = [ni() for _ in range(n)]

print(binary_search(h, a, b))


Fixed submission:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def judge(k: int, h: list, a:int, b:int):
    h = [max(0, hi - k*b) for hi in h]
    cnt = 0
    for hi in h:
        cnt += -(-hi//(a-b))

    return True if cnt <= k else False

def binary_search(h, a, b):
    low = 0
    high = 10**18

    while high - low > 1:
        mid = (high+low) // 2
        if judge(mid, h, a, b):
            high = mid
        else:
            low = mid

    return high

n, a, b = li()
h = [ni() for _ in range(n)]

print(binary_search(h, a, b))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        if idx < self.size:
            self.bitree[idx] += val
            self.addval(idx + (idx&(-idx)), val)
            
    def getsum(self, idx:int):
        if idx <= 0:
            return 0
        else:
            return self.bitree[idx] + self.getsum(idx - (idx&(-idx)))
    
    def reset(self):
        self.bitree = [0]*self.size


def val2ord(a: list, rev=False):
    dic = {ai: i for i, ai in enumerate(sorted(a, reverse=rev))}
    return [dic[ai] for ai in a]


n,k = li()
a = [ni() for _ in range(n)]

acc = [0] + list(accumulate(a))

b = [acci - i*k for i,acci in enumerate(acc)]

c = val2ord(b)

bitree = BIT(n+1)

ans = 0

for ci in c:
    bitree.addval(ci+1, 1)
    ans += bitree.getsum(ci+1)-1

print(ans)

Fixed submission:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        while idx < self.size:
            self.bitree[idx] += val
            idx += idx&(-idx)
            
    def getsum(self, idx:int):
        ret = 0
        while idx > 0:
            ret += self.bitree[idx]
            idx -= idx&(-idx)
            
        return ret
    
    def reset(self):
        self.bitree = [0]*self.size


def val2ord(a: list, rev=False):
    dic = {ai: i for i, ai in enumerate(sorted(a, reverse=rev))}
    return [dic[ai] for ai in a]


n,k = li()
a = [ni() for _ in range(n)]

acc = [0] + list(accumulate(a))

b = [acci - i*k for i,acci in enumerate(acc)]
c = val2ord(b)

bitree = BIT(n+1)

ans = 0
for ci in c:
    bitree.addval(ci+1, 1)
    ans += bitree.getsum(ci+1)-1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

n,m = li()

cnt = Counter([])
for _ in range(m):
    cnt += Counter(li())
    
exist = True
for v in cnt.values():
    if v%2:
        exist = False
        break

if exist:
    print("YES")
else:
    print("NO")

Fixed submission:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n,m  = li()
query = []
for _ in range(m):
    mi,ma = li()
    if mi > ma:
        mi,ma = ma,mi
        
    query.append((mi,ma))

root = defaultdict(list)
for l,r in query:
    root[l].append(r)


even = -1
odd = -1
for k, v in root.items():
    if len(v)%2 == 0 and even == -1:
        even = k
        
    elif len(v)%2 == 1 and odd == -1:
        odd = k

# 偶数個つながっているノードをルートに
top = even
dist = [0]*n
for l,r in query:
    if l==top:
        dist[r-1] += 1
    
    elif r==top:
        dist[l-1] += 1
    
    else:
        dist[r-1] += 1
        dist[l-1] += 1
        
exist = False
if top != -1 and all([disti % 2 == 0 for disti in dist]):
    exist = True
    

# 奇数個つながっているノードをルートに
top = odd
dist = [0]*n
for l,r in query:
    if l==top:
        dist[r-1] += 1
    
    elif r==top:
        dist[l-1] += 1
    
    else:
        dist[r-1] += 1
        dist[l-1] += 1
        
if top != -1 and all([disti % 2 == 0 for disti in dist]):
    exist = True

if exist:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()

a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai:False for ai in a_ltk}

# 貪欲に足していく
for i in range(len(a_ltk)):
    cur = 0
    stack = []
    for j in range(i,len(a_ltk)):
        cur += a_ltk[j]
        stack.append(a_ltk[j])
        if cur >= k:
            for key in stack:
                need[key] = True
            stack.pop()
            cur -= a_ltk[j]

                
cnt = Counter(a_ltk)
ans = 0

for k,v in need.items():
    if not v:
        ans += cnt[k]
        
print(ans)

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

# K以上のものはAから省く
B = []
for a in A:
    if a<K:
        B.append(a)

B.sort(reverse=True)

isNeeded = [False]*(len(B))
# iをスタックに入れる
for i in range(len(B)-1):
    res = B[i]
    stack = [i]
    for j in range(i+1,len(B)):
        res += B[j]
        stack.append(j)
        if res >= K:
            for s in stack:
                isNeeded[s] = True
            stack.pop()
            res -= B[j]
            
noNeed = len(B) - sum(isNeeded)
print(noNeed)

Buggy python submission (verdict: Runtime Error):
# 入力
file = open("g080D.txt", "r")
stdin = file

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()

a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai:False for ai in a_ltk}

# 貪欲に足していく
for i in range(len(a_ltk)):
    cur = 0
    stack = []
    for j in range(i,len(a_ltk)):
        cur += a_ltk[j]
        stack.append(a_ltk[j])
        if cur >= k:
            for key in stack:
                need[key] = True
            stack.pop()
            cur -= a_ltk[j]

                
cnt = Counter(a_ltk)
ans = 0

for k,v in need.items():
    if not v:
        ans += cnt[k]
        
print(ans)

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

# K以上のものはAから省く
B = []
for a in A:
    if a<K:
        B.append(a)

B.sort(reverse=True)

isNeeded = [False]*(len(B))
# iをスタックに入れる
for i in range(len(B)-1):
    res = B[i]
    stack = [i]
    for j in range(i+1,len(B)):
        res += B[j]
        stack.append(j)
        if res >= K:
            for s in stack:
                isNeeded[s] = True
            stack.pop()
            res -= B[j]
            
noNeed = len(B) - sum(isNeeded)
print(noNeed)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n,c,k = map(int, input().split())
t = [int(input()) for _ in range(n)]

tk = [(ti, ti+k) for ti in t]
tk.sort(key=lambda x:x[1])
tk = deque(tk)
#print(tk)


ans = 0
# tkが尽きるまで
while tk:
    _, bus = tk[0]
    
    # バスの時刻より早く来ている客をカウント
    cnt = 0
    while (tk[cnt][0] <= bus):
        cnt += 1
        
        if cnt == len(tk):
            break
        
        
    # バスの定員もしくはいる人数を乗せていく
    for _ in range(min(cnt,c)):
        tk.popleft()
    
    ans += 1
        
print(ans)
    

Fixed submission:
from collections import deque

n,c,k = map(int, input().split())
t = [int(input()) for _ in range(n)]

tk = [(ti, ti+k) for ti in t]
tk.sort(key=lambda x:x[1])
tk = deque(tk)
#print(tk)


ans = 0
# tkが尽きるまで
while tk:
    _, bus = tk[0]
    
    # バスの時刻より早く来ている客をカウント
    cnt = 0
    while (tk[cnt][0] <= bus):
        cnt += 1
        
        if cnt == len(tk):
            break
        
        
    # バスの定員もしくはいる人数を乗せていく
    for _ in range(min(cnt,c)):
        tk.popleft()
    
    ans += 1
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n, ma, mb = li()
a,b,c = list(), list(), list()
for _ in range(n):
    ai,bi,ci = li()
    a.append(ai)
    b.append(bi)
    c.append(ci)
    
INF = 10**5
dp = [[[INF for _ in range(10*n+1)] for _ in range(10*n+1)] for _ in range(n+1)]
dp[0][0][0] = 0

for dr in range(n):
    for wa in range(10*n+1):
        for wb in range(10*n+1):
            dp[dr+1][wa][wb] = min(dp[dr][wa][wb], dp[dr][wa-a[dr]][wb-b[dr]] + c[dr])
            
ans = INF
k = 1
while k*ma <= 10*n and k*mb <= 10*n:
    ans = min(ans, dp[n][k*ma][k*mb])
    k += 1
    
if ans == INF:
    print(-1)
else:
    print(ans)

Fixed submission:
import sys
sdin = sys.stdin.readline

N,Ma,Mb = map(int, sdin().split())
ABC = []
for i in range(N):
    ABC.append(tuple(map(int, sdin().split())))


sum_a = [0]
sum_b = [0]
for a,b,c in ABC:
    sum_a.append(sum_a[-1]+a)
    sum_b.append(sum_b[-1]+b)
    
INF = float("inf")
MAX_W = 400
dp = [[[INF for _ in range(sum_b[-1]+1)] for _ in range(sum_a[-1]+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0

for i, (ai, bi, ci) in enumerate(ABC):
    for a in range(sum_a[i+1]+1):
        for b in range(sum_b[i+1]+1):
            if a-ai>=0 and b-bi>=0:
                dp[i+1][a][b] = min(dp[i][a][b], dp[i][a-ai][b-bi]+ci)
            else:
                dp[i+1][a][b] = dp[i][a][b]
        
k = 1           
ans = INF
while (k*Ma<=sum_a[-1] and k*Mb<=sum_b[-1]):
    ans = min(ans, dp[N][k*Ma][k*Mb])
    k += 1
    
if ans == INF:
    print(-1)
else:
    print(ans)