Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if g[x] == []:
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(1,N+1):
    g[i] = []

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

Fixed submission:
import sys
sys.setrecursionlimit(100000000)

inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if g[x] == []:
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(1,N+1):
    g[i] = []

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if not x in g.keys():
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    if not x in g.keys():
        g[x] = []
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

Fixed submission:
import sys
sys.setrecursionlimit(100000000)

inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if g[x] == []:
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(1,N+1):
    g[i] = []

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
inp = list(map(int, input().split()))

#print(inp)
s = inp[0]
c = inp[1]

ans = 0
while(s>0):
    if s*2 <= c:
        ans += s
        c -= 2*s
        s = 0
        if c>=4:
            ans += c//4
    else:
        if c>=4:
            s += 1
            c -= 4


print (ans)


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

#print(inp)
s = inp[0]
c = inp[1]

ans = 0
if s*2 <= c:
    ans += s
    c -= 2*s
    s = 0
    if c>=4:
        ans += c//4
elif c//2<=s:
        ans += c//2
        s -= c//2
        c -= 0
else:
    if c>=4:
        ans += c//4



print (ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
line = list(map(int, input().split()))
n = N - 1
ans = 1
while(len(line) >= 0):
    c = line.count(n)
    if (len(line) == 0):
        print(ans % (10**9+7))
        break
    if len(line) == 1 and line[0] == 0:
        print(ans % (10**9+7))
        break
    elif c != 2:
        print(0)
        break
    else:
        ans *= 2
        line = [i for i in line if i != n]
        n = n - 2


Fixed submission:
N = int(input())
line = list(map(int, input().split()))
n = N - 1
ans = 1
line.sort()
s = len(line)
index = s - 1
while(index > 1):
    if line[index] == n and line[index-1] == n:
        ans *= 2
        n = n - 2
        index = index - 2
    else:
        print(0)
        break

if index == 1:
    if line[index] == n and line[index-1] == n:
        ans *= 2
        print(ans % (10**9+7))
    else:
        print(0)

elif index == 0:
    if line[0] == 0:
        print(ans % (10**9+7))
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

#for i in range(len(inp)):
i=0
c = []
for j in range(i+1,len(inp)):
    #if inp[i]<inp[j]:
    c.append(inp[j]-inp[i])
#check.append(c)
check=c
checkMax.append(max(check))

while (len(check)>1):
    check.pop(0)
    checkMax.append(max(check))


for j in range(1,len(inp)):
    checkMax[j-1] += inp[0]-inp[j]

#print (check)
#print (checkMax)
print (checkMax.count(max(checkMax)))


Fixed submission:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

#for i in range(len(inp)):
#i=0
#c = []
#for j in range(i+1,len(inp)):
    #if inp[i]<inp[j]:
#    c.append(inp[j]-inp[i])
#check.append(c)
#check=c
#checkMax.append(max(check))

#while (len(check)>1):
#    check.pop(0)
#    checkMax.append(max(check))


#for j in range(1,len(inp)):
#    checkMax[j-1] += inp[0]-inp[j]

count=0
for i in range(1,len(inp)):
    if i==1:
        mi = min(inp[0],inp[1])
        ma = inp[1]-inp[0]
        if ma>0:
            count+=1
    elif i>1:
        if ma<inp[i]-mi:
            count=1
            ma=inp[i]-mi
        elif ma==inp[i]-mi:
            count+=1
        mi = min(inp[i],mi)

print (count)


#print (check)
#print (checkMax)
#print (checkMax.count(max(checkMax)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

for i in range(len(inp)):
    c = [0]
    for j in range(i+1,len(inp)):
        if inp[i]<inp[j]:
            c.append(inp[j]-inp[i])
    check.append(c)
    checkMax.append(max(c))

#print (check)
#print (checkMax)
print (checkMax.count(max(checkMax)))




Fixed submission:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
N = int(sizes[0])
T = int(sizes[1])
line = lines[1].split(" ")
inp = []
for i in line:
    inp.append(int(i))

check = []
checkMax = []

#for i in range(len(inp)):
#i=0
#c = []
#for j in range(i+1,len(inp)):
    #if inp[i]<inp[j]:
#    c.append(inp[j]-inp[i])
#check.append(c)
#check=c
#checkMax.append(max(check))

#while (len(check)>1):
#    check.pop(0)
#    checkMax.append(max(check))


#for j in range(1,len(inp)):
#    checkMax[j-1] += inp[0]-inp[j]

count=0
for i in range(1,len(inp)):
    if i==1:
        mi = min(inp[0],inp[1])
        ma = inp[1]-inp[0]
        if ma>0:
            count+=1
    elif i>1:
        if ma<inp[i]-mi:
            count=1
            ma=inp[i]-mi
        elif ma==inp[i]-mi:
            count+=1
        mi = min(inp[i],mi)

print (count)


#print (check)
#print (checkMax)
#print (checkMax.count(max(checkMax)))
Buggy python submission (verdict: Runtime Error):
N, M = map( int, input().split() )
A = list( map( int, input().split() ) )


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [0]*(N+1)       # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


# 求めた桁数 dp[N] を用いて順序を求める
ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

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

if B % A == 0: print( A+B )
else: print( B-A )
Buggy python submission (verdict: Runtime Error):
H, W = map( int, input().split() )
S = [ list( input() ) for _ in range(H) ]

isVisited = [ [False]*W for _ in range(H) ]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# (x, y) から行けるペアの数
def dfs( x, y ):
    ans = 0
    isVisited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if S[x][y] == '#':
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '.': ans += dfs( nx, ny )+1
        else:
            if 0 <= nx and nx < H and 0 <= ny and ny < W and not isVisited[nx][ny]:
                if S[nx][ny] == '#': ans += dfs( nx, ny )+1
    return ans


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and not isVisited:
          ans += dfs( i, j )

print( ans )


Fixed submission:
N = int( input() )
H = int( input() )
W = int( input() )

print( (N-H+1)*(N-W+1) )
Buggy python submission (verdict: Runtime Error):
N, K = map( int, input().split() )
A = list( map( int, input().split() ) )

numAppeared = [0] * (N+1)

for i in A:
    numAppeared[i] += 1

numAppeared.sort( reverse=True )

# print( sum( numAppeared[i] for i in range(K,N) ) )
print( sum( numAppeared( range(K,N) ) ) )

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

numAppeared = [0] * (N+1)

for i in A:
    numAppeared[i] += 1

numAppeared.sort( reverse=True )

print( sum( numAppeared[i] for i in range(K,N) ) )
Buggy python submission (verdict: Runtime Error):
N = int( input() )

for i in range( int(N**0.5)+1 ):
    ans = max( ans, i*i )

print( ans )

Fixed submission:
N = int( input() )

ans = 0
for i in range( int(N**0.5)+1 ):
    ans = max( ans, i*i )

print( ans )
Buggy python submission (verdict: Time Limit Exceeded):
n = int( input() )
a = list( map( int, input().split() ) )


b = []
for i in range(n):
    if i%2 == 0: b.insert( 0, a[i] )
    else:        b.append( a[i] )

if n%2 == 0: b.reverse()
print( ' '.join( map(str,b)) )

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


if n%2 == 0:
    for i in range(n-1,-1,-2): print( a[i], end=' ' )
    for i in range(  0, n, 2): print( a[i], end=' ' )
else:
    for i in range(n-1,-1,-2): print( a[i], end=' ' )
    for i in range( 1 , n, 2): print( a[i], end=' ' )
Buggy python submission (verdict: Runtime Error):
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

import math
A,B,C,D=map(int,input().split())
abc=B//C-A//C
abd=B//D-A//D
abcd=(B//(lcm(C,D)))-(A//(lcm(C,D)))
if A%C==0:
    abc+=1
if A%D==0:
    abd+=1
if A%(lcm(C,D))==0:
    abcd+=1



#print(B-A+1)
#print(abc,abd,abcd)
print(B-A+1-(abc+abd-abcd))

Fixed submission:
def lcm(x, y):
    return (x * y) // gcd(x, y)
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
A,B,C,D=map(int,input().split())
abc=B//C-A//C
abd=B//D-A//D
abcd=(B//(lcm(C,D)))-(A//(lcm(C,D)))
if A%C==0:
    abc+=1
if A%D==0:
    abd+=1
if A%(lcm(C,D))==0:
    abcd+=1



#print(B-A+1)
#print(abc,abd,abcd)
print(B-A+1-(abc+abd-abcd))
Buggy python submission (verdict: Runtime Error):
A,P=map(int,input().split())
ap=A*3+P
print(ap//P)

Fixed submission:
A,P=map(int,input().split())
ap=A*3+P
print(ap//2)
Buggy python submission (verdict: Runtime Error):
a=list(input())
count=0
kekka=[]
for i in range(len(a)):
    if a[i]=="A" or a[i]=="T" or a[i]=="C" or a[i]=="G":
        count+=1
    else:
        kekka.append(count)
        count=0
print(max(kekka))

Fixed submission:
a=list(input())
count=0
kekka=[]
for i in range(len(a)):
    if a[i]=="A" or a[i]=="T" or a[i]=="C" or a[i]=="G":
        count+=1
    else:
        count=0
    kekka.append(count)
        
print(max(kekka))
Buggy python submission (verdict: Runtime Error):
T,X=map(int,input().split())
print(T/K)

Fixed submission:
T,X=map(int,input().split())
print(T/X)
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
poti=list(input().split())
poti= [ int(s) for s in poti ]
poti=sorted(poti)
sa=[]
for i in range(0,M-1):
    a=poti[i+1]-poti[i]
    sa.append(a)
#print(sa)
if len(sa)!=0:
    while len(sa)!=M-N:
        maxi=max(sa)
        sa.remove(maxi)

    print(sum(sa))

else:
    print(0)
#print(poti)

Fixed submission:
N,M=map(int,input().split())
poti=list(input().split())
poti= [ int(s) for s in poti ]
poti=sorted(poti)
sa=[]
if N>=M:
    print(0)
else:
    for i in range(0,M-1):
        a=poti[i+1]-poti[i]
        sa.append(a)


    if len(sa)!=0:  
        sa=sorted(sa)
        sa=sa[0:(M-1)-(N-1)]
        print(sum(sa))
    else:
        print(0)
Buggy python submission (verdict: Runtime Error):
s=int(input())
if s==1 or s==4 or s==2:
    print(4)
else:
    count=1
    while s!=4:
        if s%2==0:
            s=s/2
            count+=1
        else:
            s=3*s+1
            count+=1
print(count+3)
    

Fixed submission:
a=int(input())
count=1
if a==1:
  count+=3
elif a==2:
  count+=3
else:
  count+=1
  while a!=1:
    if a%2==0:
        a=a/2
        count+=1
    else:
        a=3*a+1
        count+=1
print(count)
Buggy python submission (verdict: Runtime Error):
a=int(input())
b=int(input())
c=int(input())
if a==1:
     print("Hello World")
else:
     print(b+c)

Fixed submission:
a=int(input())
if a==1:
     print("Hello World")
else:
     b=int(input())
     c=int(input())
     print(b+c)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
if a*10+b>b*10+c:
  print(a*10+b+c)
else:
  print(b*10+c+a)

Fixed submission:
a=int(input())
b=1110-a
print(b)

Buggy python submission (verdict: Runtime Error):
a=input()
b=1110-a
print(b)

Fixed submission:
a=int(input())
b=1110-a
print(b)

Buggy python submission (verdict: Runtime Error):
a=input()
b=a.translate("1":"9","9":"1")
print(b)

Fixed submission:
a=int(input())
b=1110-a
print(b)

Buggy python submission (verdict: Runtime Error):
a=str(input())
b=a.replace(1,9)
c=b.replace(9,1)
print(b)

Fixed submission:
a=int(input())
b=1110-a
print(b)

Buggy python submission (verdict: Runtime Error):
a=input()
b=a.replace(1,9)
c=b.replace(9,1)
print(b)

Fixed submission:
a=int(input())
b=1110-a
print(b)

Buggy python submission (verdict: Runtime Error):
a=input()
b=a.replace((1,9)and(9,1))
print(b)

Fixed submission:
a=int(input())
b=1110-a
print(b)
Buggy python submission (verdict: Runtime Error):
N=int(input)
a=N%111
if a==0:
   print(a*111)
else:
  b=N//111
  c=b+1
  print(c*111)
      

Fixed submission:
N=int(input())
a=N%111
if a==0:
   print(N)
else:
  b=N//111
  c=b+1
  print(c*111)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
a=str(a)
b=str(b)
c=str(c)
d=a.find("1")
e=b.find("1")
f=c.find("1")
if d+e+f=-3:
  print("0")
elif d+e+f=-2:
  print("1")
elif d+e+f=-1:
  print("2")
elif d+e+f=0:
  print("3")


Fixed submission:
a=input()
b=a.count("1")
print(b)
Buggy python submission (verdict: Time Limit Exceeded):
N, X, Y = map(int, input().split())
X = X-1
Y = Y-1

cnt = [0]*N
for i in range(N):
    for j in range(N):
        if j >= i:
            continue
        dist = min(abs(i-j),
                   abs(X-i) + abs(Y-j) + 1,
                   abs(X-j) + abs(Y-i) + 1)
        cnt[dist] += 1

print(*cnt[1:], sep='\n')


Fixed submission:
N, X, Y = map(int, input().split())
X = X-1
Y = Y-1

cnt = [0]*N
for i in range(N):
    for j in range(i+1, N):
        dist = min(abs(i-j),
                   abs(X-i) + abs(Y-j) + 1,
                   abs(X-j) + abs(Y-i) + 1)
        cnt[dist] += 1

print(*cnt[1:], sep='\n')
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
cnts = Counter(a)

_sum = 0
for key,value in cnts.items():
    _sum +=  value*(value-1)//2

for ai in a:
    ans = _sum
    c = cnts.count(ai)
    ans -= c*(c-1)//2
    ans += (c-1)*(c-2)//2
    print(ans)


Fixed submission:
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
cnts = Counter(a)

_sum = 0
for key,value in cnts.items():
    _sum +=  value*(value-1)//2

for ai in a:
    ans = _sum
    c = cnts[ai]
    ans -= c*(c-1)//2
    ans += (c-1)*(c-2)//2
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
cnts = Counter(a)

for ai in a:
    ans = 0
    for key,value in cnts.items():
        if key == ai:
            value -= 1
        ans +=  value*(value-1)//2
    print(ans)


Fixed submission:
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
cnts = Counter(a)

_sum = 0
for key,value in cnts.items():
    _sum +=  value*(value-1)//2

for ai in a:
    ans = _sum
    c = cnts[ai]
    ans -= c*(c-1)//2
    ans += (c-1)*(c-2)//2
    print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sqrt


def sieve(n: int) -> list:
    """Sieve of Eratoshenes O(N loglog N)
    return the list of is_prime (0, n]
    """
    assert n >= 1, "don't input negative value"

    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            # 素数の倍数は合成数
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return is_prime


def getDivisor(a: int) -> set:
    divisors = []
    sqrt_A = int(sqrt(a))+1
    for i in range(1, sqrt_A):
        if a % i == 0:
            divisors.append(i)
            divisors.append(a//i)
    return set(divisors)


A, B = map(int, input().split())
cd = getDivisor(A) & getDivisor(B)
# print(cd)

prime_list = sieve(max(cd))
ans = 1  # 1
for cdi in cd:
    if prime_list[cdi]:
        ans += 1
print(ans)


Fixed submission:
def factorize(a: int) -> dict:
    """素因数分解 O(sqrt(N))
    return 素因数のdict
    """
    ps = {}
    i = 2
    nokori = a
    while i*i <= nokori:
        if nokori % i == 0:
            cnt = 0
            while nokori % i == 0:
                cnt += 1
                nokori //= i
            ps[i] = cnt
        i += 1
    if nokori != 1:
        ps[nokori] = 1
    return ps


A, B = map(int, input().split())
factor_of_a = factorize(A).keys()
factor_of_b = factorize(B).keys()
ans = len(set(factor_of_a) & set(factor_of_b))
ans += 1  # 1も
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import sqrt


def sieve(n: int) -> list:
    """Sieve of Eratoshenes O(N loglog N)
    return the list of is_prime (0, n]
    """
    assert n >= 1, "don't input negative value"

    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            # 素数の倍数は合成数
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return is_prime


def getDivisor(a: int) -> set:
    divisors = []
    sqrt_A = int(sqrt(a))+1
    for i in range(1, sqrt_A):
        if a % i == 0:
            divisors.append(i)
            divisors.append(a//i)
    return set(divisors)


A, B = map(int, input().split())
cd = getDivisor(A) & getDivisor(B)
# print(cd)

prime_list = sieve(max(cd))
ans = 1  # 1
for cdi in cd:
    if prime_list[cdi]:
        ans += 1
print(ans)


Fixed submission:
def factorize(a: int) -> dict:
    """素因数分解 O(sqrt(N))
    return 素因数のdict
    """
    ps = {}
    i = 2
    nokori = a
    while i*i <= nokori:
        if nokori % i == 0:
            cnt = 0
            while nokori % i == 0:
                cnt += 1
                nokori //= i
            ps[i] = cnt
        i += 1
    if nokori != 1:
        ps[nokori] = 1
    return ps


A, B = map(int, input().split())
factor_of_a = factorize(A).keys()
factor_of_b = factorize(B).keys()
ans = len(set(factor_of_a) & set(factor_of_b))
ans += 1  # 1も
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# from pprint import pprint

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

INF = 10**18
dp = [[INF]*2**N for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        cur = dp[i][state]
        if dp[i+1][used] > cur + A[i]:
            dp[i+1][used] = dp[i][state] + A[i]

        if dp[i+1][state] > cur:
            dp[i+1][state] = cur

ans = dp[-1][-1]
print(ans if ans != INF else -1)


Fixed submission:
import sys
import itertools

N,M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(map(int, input().split())))
    C.append(sum(1<<(int(x)-1) for x in map(int, input().split())))

INF = 10**18
dp = [INF]*(1<<N)
dp[0] = 0

for n,((a,b),c) in itertools.product(range(1<<N), zip(AB,C)):
    m = n|c
    x = dp[n] + a
    if dp[m] > x:
        dp[m] = x

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from pprint import pprint

N, M = map(int, input().split())
A = []
C = []
for _ in range(
        M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

INF = 10**18
dp = [[INF]*2**N for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        dp[i+1][used] = min(dp[i+1][used], dp[i][state] + A[i])

        dp[i+1][state] = min(dp[i+1][state], dp[i][state])

ans = dp[-1][-1]
print(ans if ans != INF else -1)


Fixed submission:
import sys
import itertools

N,M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(map(int, input().split())))
    C.append(sum(1<<(int(x)-1) for x in map(int, input().split())))

INF = 10**18
dp = [INF]*(1<<N)
dp[0] = 0

for n,((a,b),c) in itertools.product(range(1<<N), zip(AB,C)):
    m = n|c
    x = dp[n] + a
    if dp[m] > x:
        dp[m] = x

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 0
for i in range(N):
  ans += i
print(ans)

Fixed submission:
N = int(input())
print(N*(N-1)//2)
Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
from math import isinf


def warshall_floyd(matrix):
    """ ワーシャルフロイド
    :param matrix:  隣接行列(到達不能はfloat("inf"))
    :return matrix
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    V = len(matrix)  # 頂点数
    for i in range(V):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3  # min(c1, c2+c3)
    return matrix


def init_matrix(V: int):
    """:param V: 頂点数
    """
    return [[float('inf')]*V for _ in range(V)]


H, W = map(int, input().split())
V = 10
matrix = init_matrix(V)
for i in range(10):
    c = map(int, input().split())
    for j, cj in enumerate(c):
        matrix[i][j] = cj

warshall_floyd(matrix)
costs = [matrix[i][1] for i in range(10)]

l = []
for _ in range(H):
    l.extend(list(map(int, input().split())))
c = Counter(l)
ans = 0


for k, v in c.items():
    if k == -1:
        continue
    ans += costs[k]*v
print(ans)


Fixed submission:
S = input()
N = len(S)
ans = [0]*N
r_switch = []
l_switch = []
cur = S[0]
for i, si in enumerate(S):
    if si != cur:
        if cur == "R":
            r_switch.append(i-1)
        else:
            l_switch.append(i-1)
        cur = si

idx = 0
for i, si in enumerate(S):
    if si == "L":
        continue
    swi = r_switch[idx]
    if i >= swi:
        idx += 1
        if idx > len(r_switch):
            break
    if (swi - i) % 2 == 0:
        ans[swi] += 1
    else:
        ans[swi + 1] += 1


idx = -1
for i, si in enumerate(reversed(S)):
    i = N-i-1
    if si == "R":
        continue

    if i <= swi:
        idx -= 1
        if idx < -N:
            break
    swi = r_switch[idx]
    if (i - swi) % 2 == 0:
        ans[swi] += 1
    else:
        ans[swi+1] += 1
print(*ans, sep=" ")