Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def factorize(a):
    factors = {}
    v = a
    p = 2
    while p*p<=a:
        if v%p==0: factors[p] = 0
        while v%p==0:
            v//=p
            factors[p]+=1
        p+=1
    if v>1: factors[v] = 1
    return factors

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

# calc lcm
lcm = {}
for a in A:
    factors_a = factorize(a)
    for k, v in factors_a.items():
        if k not in lcm or lcm[k]<v: lcm[k] = v

C = 1
for k, v in lcm.items():
    C *= pow(k, v, mod)
    C %= mod

ans = 0
for a in A:
    ans += C * pow(a, mod-2, mod)
    ans %= mod

print(ans)

Fixed submission:
def factorize(a):
    factors = {}
    v = a
    if v%2==0: factors[2]=0
    while v%2==0:
        v//=2
        factors[2]+=1
    
    p = 3
    while p*p<=a:
        if v%p==0: factors[p] = 0
        while v%p==0:
            v//=p
            factors[p]+=1
        p+=2
    if v>1: factors[v] = 1
    return factors

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

# calc lcm
lcm = {}
for a in A:
    factors_a = factorize(a)
    for k, v in factors_a.items():
        if k not in lcm or lcm[k]<v: lcm[k] = v

C = 1
for k, v in lcm.items():
    C *= pow(k, v, mod)
    C %= mod

ans = 0
for a in A:
    ans += C * pow(a, mod-2, mod)
    ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]
D = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        D[i][j] = D[j][i] = ( (L[i][0]-L[j][0])**2 + (L[i][1]-L[j][1])**2 )**0.5

M = [-1]*N
pathlist = []
def makepath(k, prev):
    if k==8: pathlist.append(M[:])
    for i in range(N):
        if M[i]>=0: continue
        M[i] = k
        makepath(k+1, i)
        M[i] = -1

makepath(0, -1)

s = 0
for p in pathlist:
    for i in range(N-1):
        s += D[p[i]][p[i+1]]
        
print(s/len(pathlist))

Fixed submission:
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]
D = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        D[i][j] = D[j][i] = ( (L[i][0]-L[j][0])**2 + (L[i][1]-L[j][1])**2 )**0.5

M = [-1]*N
pathlist = []
def makepath(k, prev):
    if k==N: pathlist.append(M[:])
    for i in range(N):
        if M[i]>=0: continue
        M[i] = k
        makepath(k+1, i)
        M[i] = -1

makepath(0, -1)

s = 0
for p in pathlist:
    for i in range(N-1):
        s += D[p[i]][p[i+1]]
        
print(s/len(pathlist))
Buggy python submission (verdict: Runtime Error):
S = input()
sep = [0]
for i in range(len(S)-1):
    if S[i]=='<' and S[i+1]=='>': sep.append(i+1)
sep.append(i+2)

S += 'X'
ans = 0
center = 0
for i in range(len(sep)-1):
    s = S[sep[i]: sep[i+1]]
    l_max = s.count('>')
    ans += max(center, l_max)
    ans += l_max*(l_max-1)//2
    r_max = s.count('<')
    ans += r_max*(r_max-1)//2
    center = r_max

ans += center
print(ans)

Fixed submission:
S = input()
sep = [0]
i=0
for i in range(len(S)-1):
    if S[i]=='<' and S[i+1]=='>': sep.append(i+1)
sep.append(i+2)

S += 'X'
ans = 0
center = 0
for i in range(len(sep)-1):
    s = S[sep[i]: sep[i+1]]
    l_max = s.count('>')
    ans += max(center, l_max)
    ans += l_max*(l_max-1)//2

    r_max = s.count('<')
    ans += r_max*(r_max-1)//2
    center = r_max

ans += center
print(ans)

Buggy python submission (verdict: Runtime Error):
S = input()
sep = [0]
for i in range(len(S)-1):
    if S[i]=='<' and S[i+1]=='>': sep.append(i+1)
sep.append(i+2)

ans = 0
center = 0
for i in range(len(sep)-1):
    s = S[sep[i]: sep[i+1]]
    l_max = s.count('>')
    ans += max(center, l_max)
    ans += l_max*(l_max-1)//2

    r_max = s.count('<')
    ans += r_max*(r_max-1)//2
    center = r_max

ans += center
print(ans)

Fixed submission:
S = input()
sep = [0]
i=0
for i in range(len(S)-1):
    if S[i]=='<' and S[i+1]=='>': sep.append(i+1)
sep.append(i+2)

S += 'X'
ans = 0
center = 0
for i in range(len(sep)-1):
    s = S[sep[i]: sep[i+1]]
    l_max = s.count('>')
    ans += max(center, l_max)
    ans += l_max*(l_max-1)//2

    r_max = s.count('<')
    ans += r_max*(r_max-1)//2
    center = r_max

ans += center
print(ans)
Buggy python submission (verdict: Runtime Error):
N=input(); print(N*(N-1)//2)

Fixed submission:
N=int(input());print(N*(N-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

x = []
for a in A:
    i = bisect.bisect_left(x,a)
    if i==0: x = [a] + x
    else: x[i-1]=a

print(len(x))

Fixed submission:
import bisect

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

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print(len(x))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

n = 0
while len(A)>0:
    n+=1
    t = A[0]
    left = []
    for a in A[1:]:
        if a>t: t=a
        else: left.append(a)
    A = left

print(n)

Fixed submission:
import bisect

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

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print(len(x))
Buggy python submission (verdict: Runtime Error):
S, T = [int(c)-1 for c in input().split()]

reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S] = 0

queue={S}

time = 1
for _ in range(4*N):
    queue_new = set()
    for q in queue:
        for v in path[q]:
            if reach[time%3][v]==-1:
                reach[time%3][v]=time
        queue_new.add(v)
		
    queue = queue_new
    time += 1

if reach[0][T]==-1:
    print(-1)
else:
    print(reach[0][T]//3)

Fixed submission:
N, M = [int(c) for c in input().split()]
path = [[] for _ in range(N)]
for i in range(M):
    u, v = [int(c) for c in input().split()]
    path[u-1].append(v-1)

S, T = [int(c)-1 for c in input().split()]

reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S] = 0

queue={S}

time = 1
for _ in range(4*N):
    queue_new = set()
    for q in queue:
        for v in path[q]:
            if reach[time%3][v]==-1:
                reach[time%3][v]=time
                queue_new.add(v)
		
    queue = queue_new
    time += 1

if reach[0][T]==-1:
    print(-1)
else:
    print(reach[0][T]//3)
Buggy python submission (verdict: Runtime Error):
N = int(input())
AB = [[int(c) for c in input().split()] for _ in range(N)]

s=0
possible=True
for a, b in sorted(AB, key=lambda x:x[1]):
    s+=a
    if s>b:
	possible = False
        break

print('Yes' if possible else 'No')

Fixed submission:
N = int(input())
AB = [[int(c) for c in input().split()] for _ in range(N)]

s=0
possible=True
for a, b in sorted(AB, key=lambda x:x[1]):
    s+=a
    if s>b:
        possible = False
        break

print('Yes' if possible else 'No')
Buggy python submission (verdict: Runtime Error):
N = int(input())
p = []
for i in range(N):
    x, y = [int(c) for c in input().split()]
    p.append((x,y))

t = {}
for i, pi in enumerate(p):
    for j, pj in enumerate(p):
        if i==j : continue
        
        dx, dy = pi[0] - pj[0], pi[1] - pj[1]
        if (dx, dy) in t:
            t[(dx, dy)] += 1
        else:
            t[(dx, dy)] = 1

print(N-max([t[k] for k in t]))


Fixed submission:
N = int(input())
p = []
for i in range(N):
    x, y = [int(c) for c in input().split()]
    p.append((x,y))

t = {}
for i, pi in enumerate(p):
    for j, pj in enumerate(p):
        if i==j : continue
        
        dx, dy = pi[0] - pj[0], pi[1] - pj[1]
        if (dx, dy) in t:
            t[(dx, dy)] += 1
        else:
            t[(dx, dy)] = 1

if N==1:
    print(1)
else:
    print(N-max([t[k] for k in t]))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(c) for c in input().split()]
a = [int(input()) for _ in range(M)]

dp = [0, 1]

for i in range(N):
    if i+1 in a:
        dp.append(0)
    else:
        dp.append(dp[i]+dp[i+1])

print(dp[-1] % 1000000007)

Fixed submission:
N, M = [int(c) for c in input().split()]
a = [int(input()) for _ in range(M)]+[-1]
j=0

dp = [0, 1]

for i in range(N):
    if i+1 == a[j]:
        dp.append(0)
        while i+1==a[j]:
            j+=1
    else:
        dp.append((dp[i]+dp[i+1]) % 1000000007)

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))

mod = 10**9+7
s = 2**n1 % mod
for dd in d:
    s += ((3**dd[0] % mod) * (2**dd[1] % mod)) % mod

print(s % mod)


Fixed submission:
def modpow(a, n, mod):
    res=1
    while n>0:
        if n & 1:
            res = res * a % mod
        n = n>>1
        a = a * a % mod
    return res


L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))

mod = 10**9+7
s = modpow(2, n1, mod)
for dd in d:
    s += (modpow(3,dd[0],mod) * modpow(2,dd[1],mod)) % mod

print(s % mod)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))
	
s = 2**n1
for dd in d:
    s += 3**dd[0] * 2**dd[1]

mod = 10**9+7
print(s % mod)

Fixed submission:
def modpow(a, n, mod):
    res=1
    while n>0:
        if n & 1:
            res = res * a % mod
        n = n>>1
        a = a * a % mod
    return res


L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))

mod = 10**9+7
s = modpow(2, n1, mod)
for dd in d:
    s += (modpow(3,dd[0],mod) * modpow(2,dd[1],mod)) % mod

print(s % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B, C, D = [int(c) for c in input().split()]
S = input() + '##'

r2 = set()
r1 = {B-1}

for i, c in enumerate(S):
    if c=='.' and (i-2 in r1 or i-1 in r1):
        r1.add(i)

for x in range(A-1, C):
    if S[x]=='#' : r0 = set()
    else:
        r0=r1|r2
        r0.discard(x)
        if S[x-1]=='.' and (x-2 in r0 or x-3 in r0):
            r0.add(x-1)
        if S[x-2]=='.' and (x-3 in r0 or x-4 in r0):
            r0.add(x-2)
                
    r2=r1
    r1=r0

out = 'Yes' if D-1 in r0 else 'No'
print(out)


Fixed submission:
N, A, B, C, D = [int(c) for c in input().split()]
S = input()

reachable = {B-1}
unreachable = set()
for i, c in enumerate(S):
    if c=='.' and (i-2 in reachable or i-1 in reachable):
        reachable.add(i)


for x in range(A, C):
    if x>=2 and S[x-1]=='#' and S[x-2]=='#':
        print('No')
        exit()

    unreachable.add(x)    
    if S[x-1]=='.' and ((x-2 in reachable and x-2 not in unreachable) or
                        (x-3 in reachable and x-3 not in unreachable) or
                        (x-1 in reachable and S[x-2]=='.' and S[x]=='.')
    ):
        unreachable.discard(x-1)
    if S[x-2]=='.' and ((x-3 in reachable and x-3 not in unreachable) or
                        (x-4 in reachable and x-4 not in unreachable)):
        unreachable.discard(x-2)
        
out = 'Yes' if D-1 in reachable and D-1 not in unreachable else 'No'
print(out)

# ##..#..
# #######
# S##.#..
# .#.##..
# #######
# .#..##.
# .#..#.#


 # #.S#.#...#.#...
 # .U.#.#...#.#...
 # ..##.#...#.#...
 # ###############
 # ...###...#.#...
 # ###############
 # ...#.##..#.#...
 # ...#.#.#.#.#...
 # ...#.#..##.#...
 # ###############
 # ...#.#...###...
 # ###############
 # ...#.#...#.##..
 # ...#.#...#.#.#.
 # ...#.#...#.#G.#
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(c) for c in input().split()]

A_plus, A_minus = [], []
for a in A:
    if a>0: A_plus.append(a)
    else: A_minus.append(a)

if len(A_minus)%2==0:
    print(sum(A_plus) - sum(A_minus))
else:
    if min(A_plus) > -max(A_minus):
        print(sum(A_plus) - sum(A_minus) + max(A_minus)*2)
    else:
        print(sum(A_plus) - sum(A_minus) - min(A_plus)*2)
        


Fixed submission:
N = int(input())
A = [int(c) for c in input().split()]

A_plus, A_minus = [], []
for a in A:
    if a>0: A_plus.append(a)
    else: A_minus.append(a)

if len(A_minus)%2==0:
    print(sum(A_plus) - sum(A_minus))
elif len(A_plus)==0:
    print(sum(A_plus) - sum(A_minus) + max(A_minus)*2)    
else:
    if min(A_plus) > -max(A_minus):
        print(sum(A_plus) - sum(A_minus) + max(A_minus)*2)
    else:
        print(sum(A_plus) - sum(A_minus) - min(A_plus)*2)
Buggy python submission (verdict: Runtime Error):
N, K = [int(c) for c in input().split()]
S = [int(c) for c in input()]

longest=0

for bgn_flip in range(len(S)):

    S_copy=S[:]
    zero=False
    icluster=-1
    for i,s in enumerate(S):
        if s==0 and zero==False:
            zero=True
            icluster+=1
        if s==1:
            zero=False

        if s==0 and icluster>=bgn_flip and icluster < bgn_flip+K:
       	    S_copy[i]=1

    seq=0
    for sc in S_copy:
        if sc==1: seq+=1
        if sc==0: seq=0
        if seq>longest:longest=seq

print(longest)

Fixed submission:
A,B = [int(c) for c in input().split()]
if A>B:
    print(A*2-1)
elif A==B:
    print(A*2)
else:
    print(B*2-1)
Buggy python submission (verdict: Runtime Error):
S = input()
n = []
k=0
for c in S:
    if c in 'ACGT':
        k+=1
    elif k>0:
        n.append(k)
        k=0
if k>0: n.append(k)

print(max(n))

Fixed submission:
S = input()
n = [0]
k=0
for c in S:
    if c in 'ACGT':
        k+=1
    elif k>0:
        n.append(k)
        k=0
if k>0: n.append(k)

print(max(n))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
for n in range(N,M+1):
    if M%n==0:
        print(M//n)
        break

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

f1, f2 = [], []

k = 1
while k*k<=M:
    if M%k==0:
        f1.append(k)
        f2.append(M//k)
    k+=1

for f in f1 + list(reversed(f2)):
    if f>=N:
        print(M//f)
        break
Buggy python submission (verdict: Runtime Error):
N, i = map(int, input())
print(N-i+1)

Fixed submission:
N, i = map(int, input().split())
print(N-i+1)
Buggy python submission (verdict: Runtime Error):
N = int(''.join(input().split()))
sq = False
for k in range(1, N):
  sq |= k*k==N:
print('Yes' if sq else 'No')

Fixed submission:
N = int(''.join(input().split()))
sq = False
for k in range(1, N):
  sq |= k*k==N
print('Yes' if sq else 'No')
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
K = (N+1)//2
X = set()
if N&1:
  X = {S[K-1]}
  l = K-2
  r = K
else:
  X = set()
  l = K-1
  r = K
  
while l:
  X.add(S[l])
  X.add(S[r])
  if len(X)>1: break
  K += 1
  l -= 1
  r += 1

print(K)

Fixed submission:
S = input()
N = len(S)

if len(set(S))==1:
  print(N)
  exit()

K = (N+1)//2
X = set()
if N&1:
  X = {S[K-1]}
  l = K-2
  r = K
else:
  X = set()
  l = K-1
  r = K
  
while l:
  X.add(S[l])
  X.add(S[r])
  if len(X)>1: break
  K += 1
  l -= 1
  r += 1

print(K)
Buggy python submission (verdict: Runtime Error):
s = input()
x, y = list(map(int, input().split()))
F = [len(fs) for fs in s.split('T')]
Fx = F[0::2]
Fy = F[1::2]

xt2 = sum(Fx)-x
yt2 = sum(Fy)-y
if xt2%2==1 or yt2%2==1:
    print('No')
    exit()

xt = xt2//2
yt = yt2//2

dpx = [False]*(xt+1)
dpx[0] = True
for f in Fx:
    for i in range(xt, f-1, -1): dpx[i] |= dpx[i-f]

dpy = [False]*(yt+1)
dpy[0] = True
for f in Fy:
    for i in range(yt, f-1, -1): dpy[i] |= dpy[i-f]

print('Yes' if dpx[xt] and dpy[yt] else 'No')

Fixed submission:
s = input()
x, y = list(map(int, input().split()))
F = [len(fs) for fs in s.split('T')]
x -= F[0]
Fx = F[2::2]
Fy = F[1::2]

xt2 = sum(Fx)-x
yt2 = sum(Fy)-y
if xt2%2==1 or yt2%2==1 or xt2<0 or yt2<0:
    print('No')
    exit()

xt = xt2//2
yt = yt2//2

dpx = [False]*(xt+1)
dpx[0] = True
for f in Fx:
    for i in range(xt, f-1, -1): dpx[i] |= dpx[i-f]

dpy = [False]*(yt+1)
dpy[0] = True
for f in Fy:
    for i in range(yt, f-1, -1): dpy[i] |= dpy[i-f]

print('Yes' if dpx[xt] and dpy[yt] else 'No')

Buggy python submission (verdict: Runtime Error):
s = input()
x, y = list(map(int, input().split()))
F = [len(fs) for fs in s.split('T')]
Fx = F[0::2]
Fy = F[1::2]

xt2 = (sum(Fx)-x)
yt2 = (sum(Fy)-y)
if xt2%2==1 or yt2%2==1:
    print('No')
    exit()

xt = xt2//2
yt = yt2//2

M = 8000
dpx = [False]*M
dpx[0] = True
for f in Fx:
    for i in range(M-1, f-1, -1):
        if dpx[i-f]: dpx[i]=True

dpy = [False]*M
dpy[0] = True
for f in Fy:
    for i in range(M-1, f-1, -1):
        if dpy[i-f]: dpy[i]=True

print('Yes' if dpx[xt] and dpy[yt] else 'No')

Fixed submission:
s = input()
x, y = list(map(int, input().split()))
F = [len(fs) for fs in s.split('T')]
x -= F[0]
Fx = F[2::2]
Fy = F[1::2]

xt2 = sum(Fx)-x
yt2 = sum(Fy)-y
if xt2%2==1 or yt2%2==1 or xt2<0 or yt2<0:
    print('No')
    exit()

xt = xt2//2
yt = yt2//2

dpx = [False]*(xt+1)
dpx[0] = True
for f in Fx:
    for i in range(xt, f-1, -1): dpx[i] |= dpx[i-f]

dpy = [False]*(yt+1)
dpy[0] = True
for f in Fy:
    for i in range(yt, f-1, -1): dpy[i] |= dpy[i-f]

print('Yes' if dpx[xt] and dpy[yt] else 'No')
Buggy python submission (verdict: Runtime Error):
N = input(input())
k = 1
while k*k<=N: k+=1
print((k-1)*(k-1))

Fixed submission:
N = int(input())
k = 1
while k*k<=N: k+=1
print((k-1)*(k-1))
Buggy python submission (verdict: Runtime Error):
X, t = list(map(int,input().split()))
print(max(X-t),0)

Fixed submission:
X, t = list(map(int,input().split()))
print(max(X-t,0))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
M = [0]*(N+10)
for a in A:
    for i in range(3): M[a+i]+=1
print(max(M))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
M = [0]*(10**5+10)
for a in A:
    for i in range(3): M[a+i]+=1
print(max(M))
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(N):
    if P[i]==i+1:
        P[i+1]=P[i]
        ans+=1
print(ans)

Fixed submission:
N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(N-1):
    if P[i]==i+1:
        P[i+1]=P[i]
        ans+=1
if P[N-1]==N: ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
A = map(int, input().split())
print(sum(A)-max(A))

Fixed submission:
A = list(map(int, input().split()))
print(sum(A)-max(A))
Buggy python submission (verdict: Runtime Error):
s = input()
for k in range(len(s)//2-1, 0, -1)
  if s[:k] == s[k:2*k]: break
print(k)

Fixed submission:
s = input()
for k in range(len(s)//2-1, 0, -1):
  if s[:k] == s[k:2*k]: break
print(k*2)
Buggy python submission (verdict: Time Limit Exceeded):
N, Ma, Mb = list(map(int, input().split()))
D = [tuple(map(int, input().split())) for _ in range(N)]

def dfs(L, D, i, ta, tb, tc):
    if i==len(D):
        key = (ta, tb)
        L[key] = min(L[key], tc) if key in L else tc
        return
    a, b, c = D[i]
    dfs(L, D, i+1, ta  , tb  , tc  )
    dfs(L, D, i+1, ta+a, tb+b, tc+c)

L1, L2 = {}, {}
dfs(L1, D[:N//2], 0, 0, 0, 0)
dfs(L2, D[N//2:], 0, 0, 0, 0)

ans = 10**9
for m in range(1,401):
    ma = Ma * m
    mb = Mb * m
    if ma>400 or mb>400: break
    for key1 in L1:
        ta1, tb1 = key1
        ta2 = ma - ta1
        tb2 = mb - tb1
        key2 = (ta2, tb2)
        if key2 in L2: ans = min(ans, L1[key1]+L2[key2])

print(ans if ans!=10**9 else -1)

Fixed submission:
N, Ma, Mb = list(map(int, input().split()))
D = [tuple(map(int, input().split())) for _ in range(N)]

def listup(L, D):
    for a, b, c in D:
        for (ka, kb), kc in L.copy().items():
            key = (ka+a, kb+b)
            L[key] = min(L[key], kc+c) if key in L else kc+c
        

L1 = {(0,0):0}
L2 = {(0,0):0}
listup(L1, D[:N//2])
listup(L2, D[N//2:])

ans = 10**9
for m in range(1,401):
    ma = Ma * m
    mb = Mb * m
    if ma>400 or mb>400: break
    for key1 in L1:
        ta1, tb1 = key1
        ta2 = ma - ta1
        tb2 = mb - tb1
        key2 = (ta2, tb2)
        if key2 in L2: ans = min(ans, L1[key1]+L2[key2])

print(ans if ans!=10**9 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, Ma, Mb = list(map(int, input().split()))
D = [tuple(map(int, input().split())) for _ in range(N)]

def dfs(L, D, i, ta, tb, tc):
    if i==len(D):
        key = (ta, tb)
        L[key] = min(L[key], tc) if key in L else tc
        return
    a, b, c = D[i]
    dfs(L, D, i+1, ta  , tb  , tc  )
    dfs(L, D, i+1, ta+a, tb+b, tc+c)

L1, L2 = {}, {}
dfs(L1, D[:N//2], 0, 0, 0, 0)
dfs(L2, D[N//2:], 0, 0, 0, 0)

ans = 10**9
for m in range(1,401):
    ma = Ma * m
    mb = Mb * m
    for key1 in L1:
        ta1, tb1 = key1
        ta2 = ma - ta1
        tb2 = mb - tb1
        key2 = (ta2, tb2)
        if key2 in L2: ans = min(ans, L1[key1]+L2[key2])

print(ans if ans!=10**9 else -1)

Fixed submission:
N, Ma, Mb = list(map(int, input().split()))
D = [tuple(map(int, input().split())) for _ in range(N)]

def listup(L, D):
    for a, b, c in D:
        for (ka, kb), kc in L.copy().items():
            key = (ka+a, kb+b)
            L[key] = min(L[key], kc+c) if key in L else kc+c
        

L1 = {(0,0):0}
L2 = {(0,0):0}
listup(L1, D[:N//2])
listup(L2, D[N//2:])

ans = 10**9
for m in range(1,401):
    ma = Ma * m
    mb = Mb * m
    if ma>400 or mb>400: break
    for key1 in L1:
        ta1, tb1 = key1
        ta2 = ma - ta1
        tb2 = mb - tb1
        key2 = (ta2, tb2)
        if key2 in L2: ans = min(ans, L1[key1]+L2[key2])

print(ans if ans!=10**9 else -1)
Buggy python submission (verdict: Runtime Error):
H, W = list(map(int, input().split()))
for _ in H:
    S = input()
    print(S)
    print(S)

Fixed submission:
H, W = list(map(int, input().split()))
for _ in range(H):
    S = input()
    print(S)
    print(S)
Buggy python submission (verdict: Runtime Error):
def dividable(S):
    return ((S[:5]=='dream'   and dividable(S[5:])) or
            (S[:7]=='dreamer' and dividable(S[7:])) or
            (S[:5]=='erase'   and dividable(S[5:])) or
            (S[:6]=='eraser'  and dividable(S[6:])) or
            (S==''))

print('YES' if dividable(input()) else 'NO')

Fixed submission:
S = [input()]
ans = 'NO'
while S:
    S_new = []
    for s in S:
        if s[:5]=='dream'  : S_new.append(s[5:])
        if s[:7]=='dreamer': S_new.append(s[7:])
        if s[:5]=='erase'  : S_new.append(s[5:])
        if s[:6]=='eraser' : S_new.append(s[6:])
    S = S_new
    if '' in S:
        ans = 'YES'
        break

print(ans)
Buggy python submission (verdict: Runtime Error):
# 文字が2種類になるまで減る
# 2種類になったら終了
# 両端の文字が違うならその2種類が残る→偶数個残る
# 両端の文字が同じならその文字+1種→奇数個残る

s = input()
iseven = len(S)&1==0
issame = S[0]==S[-1]
print('First' if iseven^issame else 'Second')

Fixed submission:
# 文字が2種類になるまで減る
# 2種類になったら終了
# 両端の文字が違うならその2種類が残る→偶数個残る
# 両端の文字が同じならその文字+1種→奇数個残る

s = input()
iseven = len(s)&1==0
issame = s[0]==s[-1]
print('Second' if iseven^issame else 'First')
Buggy python submission (verdict: Runtime Error):
s = input()
for x in map(chr, range(ord('a'), ord('z')+1)):
    p = None
    for i, c in enumerate(s):
        if c!=x: continue
        if p:
            print(p+1, i+1)
            exit()
	p = i

print(-1, -1)

Fixed submission:
s = input()
for x in list(map(chr, range(ord('a'), ord('z')+1))):
    p = None
    for i, c in enumerate(s):
        if c!=x: continue
        if p is not None and i-p<=2:
            print(p+1, i+1)
            exit()
        p = i

print(-1, -1)
Buggy python submission (verdict: Runtime Error):
S = int(input())

DP = [0]*(S+1)
DP[0] = 0
DP[1] = 0
DP[2] = 0

for i in range(3, S + 1):
  DP[i] += 1
  for j in range(i - 3 + 1):
    DP[i] += DP[j]

print(DP[S] % (10 ** 9 + 7))


Fixed submission:
S = int(input())

if S < 3:
  print(0)
  import sys
  sys.exit()

DP = [0]*(S+1)
DP[0] = 0
DP[1] = 0
DP[2] = 0

for i in range(3, S + 1):
  DP[i] += 1
  for j in range(i - 3 + 1):
    DP[i] += DP[j]

print(DP[S] % (10 ** 9 + 7))