Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy
N=int(input())
A=[int(i) for i in input().split()]

def chmax(a,b):
    if a[0]<b[1]:
        return b
    elif a[0]<b[0]:
        return(b[0],a[0])
    elif a[1]<b[0]:
        return (a[0],b[0])
    else:
        return a
dp=[(A[i],0) for i in range(1<<N)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if (j & (1<<i))==0:
            #print(j,i,j|(1<<i))
            dp[j|(1<<i)]=chmax(dp[j],dp[j|(1<<i)])
#print(dp)
ans =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)

Fixed submission:
from copy import deepcopy
N=int(input())
A=[int(i) for i in input().split()]

def chmax(a,b):
    if a[0]<b[1]:
        return b
    elif a[0]<b[0]:
        return(b[0],a[0])
    elif a[1]<b[0]:
        return (a[0],b[0])
    else:
        return a
dp=[(A[i],0) for i in range(1<<N)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if j & (1<<i):
            #print(j,i,j|(1<<i))
            dp[j]=chmax(dp[j],dp[j^(1<<i)])
#print(dp)
ans =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N,C = map(int,input().split())
D=[[int(i) for i in input().split()] for j in range(C)]
co=[[int(i) for i in input().split()] for j in range(N)]
d0= defaultdict(int)
d1= defaultdict(int)
d2= defaultdict(int)
for i in range(N):
    for j in range(N):
        if (j+i) %3==0:
            d0[co[j][i]] +=1
        elif (j+i)%3==1:
            d1[co[j][i]] +=1
        else:
            d2[co[j][i]] +=1
A0=[]#i色に帰るのに必要な違和感
A1=[]
A2=[]
for i in range(C):
    iwa =0
    for s in d0.keys():
        iwa += D[s-1][i-1]*d0[s] 
    A0.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d1.keys():
        iwa += D[s-1][i-1]*d1[s] 
    A1.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d2.keys():
        iwa += D[s-1][i-1]*d2[s] 
    A2.append([iwa,i])

A0.sort()
A1.sort()
A2.sort()
B=[[] for i in range(3)]
for i in range(3):
    B[0].append(A0[i])
for i in range(3):
    B[1].append(A1[i])
for i in range(3):
    B[2].append(A2[i])
ans =[]
for i in range(3):
    for j in range(3):
        for k in range(3):
            if B[0][i][1] ==B[1][j][1]:
                continue
            if B[0][i][1] ==B[2][k][1]:
                continue
            if B[1][j][1] ==B[2][k][1]:
                continue
            ans.append(B[0][i][0]+B[1][j][0]+B[2][k][0])
print(min(ans))


Fixed submission:
N = int(input())
A=[]
A.append(1)
for i in range(1,7):
    A.append(6**i)
for i in range(1,6):
    A.append(9**i)
A.sort()
dp=[10*5+5]*(N+1)
dp[0]=0
for i in range(1,N+1):
    for s in range(len(A)):
        if i-A[s]>=0:
            dp[i]=min(dp[i-A[s]]+1,dp[i])
print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
N,C = map(int,input().split())
D=[[int(i) for i in input().split()] for j in range(C)]
co=[[int(i) for i in input().split()] for j in range(N)]
A=[[0]*C for i in range(3)]#iに変えた時の違和感
for i in range(N):
    for j in range(N):
        t = (i+j)%3
        for s in range(C):
            A[t][s]+=D[co[j][i]-1][s]
ans =10**13
for x in range(C):
    for y in range(C):
        if x==y:
            continue
        for z in range(C):
            if x==z or y==z:
                continue
            ans=min(ans,A[0][x]+A[1][y]+A[2][z])
print(ans)

Fixed submission:
from collections import defaultdict
N,C = map(int,input().split())
D=[[int(i) for i in input().split()] for j in range(C)]
co=[[int(i) for i in input().split()] for j in range(N)]
d0= defaultdict(int)
d1= defaultdict(int)
d2= defaultdict(int)
for i in range(N):
    for j in range(N):
        if (j+i) %3==0:
            d0[co[j][i]] +=1
        elif (j+i)%3==1:
            d1[co[j][i]] +=1
        else:
            d2[co[j][i]] +=1
A0=[]#i色に帰るのに必要な違和感
A1=[]
A2=[]
for i in range(C):
    iwa =0
    for s in d0.keys():
        iwa += D[s-1][i-1]*d0[s] 
    A0.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d1.keys():
        iwa += D[s-1][i-1]*d1[s] 
    A1.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d2.keys():
        iwa += D[s-1][i-1]*d2[s] 
    A2.append([iwa,i])

A0.sort()
A1.sort()
A2.sort()
B=[[] for i in range(3)]
for i in range(3):
    B[0].append(A0[i])
for i in range(3):
    B[1].append(A1[i])
for i in range(3):
    B[2].append(A2[i])
ans =[]
for i in range(3):
    for j in range(3):
        for k in range(3):
            if B[0][i][1] ==B[1][j][1]:
                continue
            if B[0][i][1] ==B[2][k][1]:
                continue
            if B[1][j][1] ==B[2][k][1]:
                continue
            ans.append(B[0][i][0]+B[1][j][0]+B[2][k][0])
print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A=[int(i) for i in input().split()]
S=[0]
S.append(A[0])
for i in range(1,N):
    a = S[-1] + A[i]
    S.append(a)
T =[0]
T.append(A[0])
for i in range(1,N):
    a = T[-1]^A[i]
    T.append(a)
ans = 0
for r in range(1,N+1):
    for l in range(r):
        if S[r]-S[l] == T[r]^T[l]:
            ans+=1
print(ans)

Fixed submission:
N = int(input())
A=[int(i) for i in input().split()]
L = []
asum=A[0]
axor=A[0] 
i=0
j=0
while (i<N):
    while (asum ==axor) and (j<N-1):
        j = j+1
        asum += A[j]
        axor ^= A[j]
    if (j<N-1):
        L.append((i,j-1))
        asum -= A[i]
        axor ^= A[i] 
        i += 1
    elif (asum ==axor):
        L.append((i,N-1))
        i += 1 
    else:
        L.append((i,j-1))
        asum -= A[i]
        axor ^= A[i] 
        i += 1
ans = 0
for l,r in L:
    ans += r-l+1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())
L = set([])
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        L.add(s[i:j])
print(sorted(L)[K-1])

Fixed submission:
s = input()
K = int(input())
L = set([])
for i in range(len(s)):
    for j in range(i+1,min(i+6,len(s)+1)):
        L.add(s[i:j])
print(sorted(L)[K-1])
Buggy python submission (verdict: Runtime Error):
L=[	7151,8111,8741,8431,9241,11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291]
print(L.join(map(str,[3,4,5][:int(input())])))


Fixed submission:
L=[2,11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,
  401,421,431,461,491,521,541,571,601,631,641,661,701,751,761,811,821,
  881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,
  1201,1231,1291, 1301,1321,1361,1381,1451,1471]
N = int(input())
A = []
for i in range(N):
    A.append(L[i])
print(' '.join(map(str, A)))
Buggy python submission (verdict: Time Limit Exceeded):
N,C = map(int,input().split())
table=[]
for i in range(N):
    x,v=map(int,input().split())
    table.append([x,v])
V=[0]*N
V[0]=table[0][1]
for i in range(1,N):
    V[i]=V[i-1]+table[i][1]
ans=0
for i in range(N):
    #print(V[i]-table[i][0])
    ans=max(ans,V[i]-table[i][0])
for i in range(N-1,0,-1):
    #print(V[N-1]-V[i-1]-C+table[i][0])
    ans = max(ans,V[N-1]-V[i-1]-C+table[i][0])
ans=max(ans,V[N-1]-C+table[0][0])
#print(V[N-1]-C+table[0][0])
#print(1)
for i in range(N):
    for k in range(i+1,N):
        #print(V[i]+V[N-1]-V[k-1]-C-2*table[i][0]+table[k][0])
        #print(V[i]+V[N-1]-V[k-1]-table[i][0]-2*C+2*table[k][0])
        ans = max(ans, V[i]+V[N-1]-V[k-1]-C-2*table[i][0]+table[k][0])
        ans = max(ans,V[i]+V[N-1]-V[k-1]-table[i][0]-2*C+2*table[k][0])
print(ans)

Fixed submission:
import sys
N,C = map(int,input().split())
table=[]
for i in range(N):
    x,v=map(int,input().split())
    table.append([x,v])
ans=0
if N==1:
    ans=max(0,table[0][1]-table[0][0],table[0][1]+table[0][0]-C)
    print(ans)
    sys.exit()
V=[0]*N
clo=[0]*N
V[0]=table[0][1]
clo[0]=V[0]-table[0][0]
for i in range(1,N):
    V[i]=V[i-1]+table[i][1]
    clo[i]=max(clo[i-1],V[i]-table[i][0])
    ans = max(clo[i],ans)
rclo=[0]*N
rclo[N-1]=V[N-1]-V[N-2]-C+table[N-1][0]
for i in range(N-1,1,-1):
    rclo[i-1]=max(rclo[i],V[N-1]-V[i-2]-C+table[i-1][0])
    ans = max(clo[i],ans)
rclo[0]=max(rclo[1],V[N-1]-C+table[0][0])
ans = max(rclo[0],ans)

for i in range(N-1):
    t = V[i]+rclo[i+1]-2*table[i][0]
    ans=max(t,ans)
for i in range(N-1,0,-1):
    t = V[N-1]-V[i-1] + clo[i-1]-2*C+2*table[i][0]
    ans=max(t,ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
N = int(input())
A =[int(i) for i in input().split()]
a = max(A)
if a%2==0:
    s =a//2
    for i in A:
        if i <=s:
            seco=max(seco,i)
        else:
            seco=max(seco,a-i)
else:
    seco=0
    s = a//2 +1
    for i in A:
        if i <=s:
            seco=max(seco,i)
        else:
            seco=max(seco,a-i)

for i in A:
    if i==seco:
        print(a,seco)
        sys.exit()
print(a,a-seco)

Fixed submission:
import sys
N = int(input())
A =[int(i) for i in input().split()]
a = max(A)
if a%2==0:
    seco=0
    s =a//2
    for i in A:
        if i <=s:
            seco=max(seco,i)
        else:
            seco=max(seco,a-i)
else:
    seco=0
    s = a//2 +1
    for i in A:
        if i <=s:
            seco=max(seco,i)
        else:
            seco=max(seco,a-i)

for i in A:
    if i==seco:
        print(a,seco)
        sys.exit()
print(a,a-seco)
Buggy python submission (verdict: Runtime Error):
from math import sqrt 
Q = int(input())
table=[]
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        table.append([B,A])
    else:
        table.append([A,B])
def f(a,b):
    if a==b:
        return 2*a-2
    if a+1==b:
        return 2*a-2
    m = int(sqrt(a*b))
    if m**2 ==a*b:
        return 2*m-3
    if m*(m+1) >= a*b:
        return 2*m -2
    return 2*m-1

ans = []
for a,b in table:
    ans.append(f(a,b))
print('\n'.join(map(str,ans)))

Fixed submission:
A,B,C=map(int,input().split())
L=[A,B,C]
L.sort()
ans=0
s=(L[-1]-L[0])//2
L[0]=L[0]+2*s
t=(L[-1]-L[1])//2
L[1]=L[1]+2*t
L.sort()
a=0
if L[0]!=L[1]:
    a=2
elif L[1]!=L[2]:
    a=1
print(s+t+a)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dd=defaultdict(int)
for i in range(3):
    dd[(0,i,i)]=1
for k in range(2,N+1):
    nd=defaultdict(int)
    for p,n in dd.items():
        con,moji,m=p
        #print(con,moji,m)
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[(1, k, (m + k) % 3)] += n
                    nd[(1, k, (m + k) % 3)] %=mod
                else:
                    nd[(0,k,(m+k)%3)]+=n
                    nd[(0, k, (m+k) % 3)] %=mod
        else:
            for k in range(3):
                nd[(1, k, (m + k) % 3)] += n
                nd[(1, k, (m + k) % 3)] %=mod
    #print(nd)
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for p, n in dd.items():
    con, moji, m = p
    if m==M and con==1:
        ans+=n
        ans%=mod
print(ans)






Fixed submission:
from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
a=S[0]
t=1
for i in range(N):
    if S[i]!=a:
        t=0
        break
if t==1:
    print(1)
    sys.exit()

mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dp=[]
for i in range(2):
    for k in range(3):
        for l in range(3):
            dp.append((i,k,l))
dd=[[[0]*3 for i in range(3)] for i in range(2)]
for i in range(3):
    dd[0][i][i]=1
for k in range(2,N+1):
    nd=[[[0]*3 for i in range(3)] for i in range(2)]
    for p in dp:
        con,moji,m=p
        n=dd[con][moji][m]
        #print(con,moji,m)
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[1][k][ (m + k) % 3] += n
                    nd[1] [k ][(m + k) % 3] %=mod
                else:
                    nd[0][k][(m+k)%3]+=n
                    nd[0][ k] [(m+k) % 3] %=mod
        else:
            for k in range(3):
                nd[1][k][(m + k) % 3] += n
                nd[1][k][(m + k) % 3] %=mod
    #print(nd)
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for k in range(3):
    ans+=dd[1][k][M]
    ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
class WeightUnionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)
        self.weight=[0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            r = self.find(self.par[x])
            self.weight[x]+=self.weight[self.par[x]]
            self.par[x]=r
            return self.par[x]
        
    def weighted(self,x):
        self.find(x)
        return self.weight[x]
    
    def union(self,x,y,w):#weight(y) = weight(x) + w となるように x と y をマージする
        w += self.weighted(x)
        w -= self.weighted(y)
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
            self.weight[px]=-w
        else:
            self.par[py]=px
            self.weight[py] = w
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
    def diff(self,x,y):
        return self.weighted(y-self.weighted(x)
    
N,M = map(int,input().split())
Tree = WeightUnionfindtree(N)
ans = 'Yes'
for i in range(M):
    L,R,D = map(int,input().split())
    if Tree.connect(L-1,R-1):
        if Tree.diff(L-1,R-1)!=D:
            ans = 'No'
    else:
        Tree.union(L-1,R-1,D)
print(ans)

Fixed submission:
class WeightUnionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)
        self.weight=[0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            r = self.find(self.par[x])
            self.weight[x]+=self.weight[self.par[x]]
            self.par[x]=r
            return self.par[x]
        
    def weighted(self,x):
        self.find(x)
        return self.weight[x]
    
    def union(self,x,y,w):#weight(y) = weight(x) + w となるように x と y をマージする
        w += self.weighted(x)
        w -= self.weighted(y)
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
            self.weight[px]=-w
        else:
            self.par[py]=px
            self.weight[py] = w
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
    def diff(self,x,y):
        return self.weighted(y)-self.weighted(x)
    
N,M = map(int,input().split())
Tree = WeightUnionfindtree(N)
ans = 'Yes'
for i in range(M):
    L,R,D = map(int,input().split())
    if Tree.connect(L-1,R-1):
        if Tree.diff(L-1,R-1)!=D:
            ans = 'No'
    else:
        Tree.union(L-1,R-1,D)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
Graph =[[] for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    Graph[L-1].append((R-1,D))
    Graph[R-1].append((L-1 ,-D))
visit=[False]*N
for i in range(N):
    if visit[i]==False:
        visit[i]=0
        A = deque()
        A.append(i)
        while A:
            x = A.pop()
            for y,d in Graph[x]:
                if (visit[y] != False) and (visit[y]!=d+visit[x]):
                    print('No')
                    sys.exit()
                elif (visit[y] == False):
                    A.append(y)
                    visit[y]=d+visit[x] 
    
print('Yes')

Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
Graph =[[] for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    Graph[L-1].append((R-1,D))
    Graph[R-1].append((L-1 ,-D))
visit=[False]*N
dist=[0]*N
for i in range(N):
    if visit[i]==False:
        visit[i]=True
        A = deque()
        A.append(i)
        while A:
            x = A.pop()
            for y,d in Graph[x]:
                if (visit[y] == True) and (dist[y]!=d+dist[x]):
                    print('No')
                    sys.exit()
                elif (visit[y] == False):
                    visit[y]=True
                    A.append(y)
                    dist[y]=d+dist[x] 
    
print('Yes')
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_right,bisect_left
import sys
N,H = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
B.sort()
ama=max(A)
x = bisect_right(B,ama)
ans = 0
if x ==N:
    if H%ama ==0:
        ans += H//ama 
    else:
        ans += H//ama +1
    print(ans)
    sys.exit()
for i in range(N-1,x-1,-1):
    if H<=0:
        print(ans)
        sys.exit()
    else H>0:
        H-=B[i]
        ans +=1
if H>0:
    if H%ama ==0:
        ans += H//ama 
    else:
        ans += H//ama +1
print(ans)

Fixed submission:
from bisect import bisect_right,bisect_left
import sys
N,H = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
B.sort()
ama=max(A)
x = bisect_right(B,ama)
ans = 0
if x ==N:
    if H%ama ==0:
        ans += H//ama 
    else:
        ans += H//ama +1
    print(ans)
    sys.exit()
for i in range(N-1,x-1,-1):
    if H<=0:
        print(ans)
        sys.exit()
    else:
        H-=B[i]
        ans +=1
if H>0:
    if H%ama ==0:
        ans += H//ama 
    else:
        ans += H//ama +1
print(ans)
Buggy python submission (verdict: Runtime Error):
N,C =map(int,input().split())
chan=[[] for i in range(C)]
for i in range(N):
    a,b,c=map(int,input().split())
    chan[c-1].append([a,b])
for i in range(C):
    chan[i].sort()
imos=[0]*(10**5+1)
for i in range(C):
    if len(chan[i])==0:
        continue
    imos[chan[i][0][0]]+=1
    imos[chan[i][0][1]+1]-=1
    for k in range(1,len(chan[i])):
        if chan[i][k][0]==chan[i][k-1][1]:
            imos[chan[i][k][0]+1]+=1
            imos[chan[i][k][1]+1]-=1
        else:
            imos[chan[i][k][0]]+=1
            imos[chan[i][k][1]+1]-=1

for i in range(1,10**5+1):
     imos[i] +=imos[i-1]  
print(max(imos))

Fixed submission:
N,C =map(int,input().split())
chan=[[] for i in range(C)]
for i in range(N):
    a,b,c=map(int,input().split())
    chan[c-1].append([a,b])
for i in range(C):
    chan[i].sort()
imos=[0]*(10**5+2)
for i in range(C):
    if len(chan[i])==0:
        continue
    imos[chan[i][0][0]]+=1
    imos[chan[i][0][1]+1]-=1
    for k in range(1,len(chan[i])):
        if chan[i][k][0]==chan[i][k-1][1]:
            imos[chan[i][k][0]+1]+=1
            imos[chan[i][k][1]+1]-=1
        else:
            imos[chan[i][k][0]]+=1
            imos[chan[i][k][1]+1]-=1

for i in range(1,10**5+2):
     imos[i] +=imos[i-1]  
print(max(imos))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[]
for i in range(N):
    h,p=map(int,input().split())
    A.append((h+p,h,p))
A.sort()


dp=[[10**23]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    for j in range(1,N+1):
        #print(A[i-1])
        if dp[i-1][j-1]>A[i-1][1]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+A[i-1][2])
for j in range(N,-1,-1):
    if dp[N][j]<10**23:
        print(j)
        break

Fixed submission:
N=int(input())
A=[]
for i in range(N):
    h,p=map(int,input().split())
    A.append((h+p,h,p))
A.sort()
dp=[[10**13]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    s=A[i-1][1]
    t=A[i-1][2]
    for j in range(1,i+1):
        #print(A[i-1])
        if dp[i-1][j-1]>s:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+t)
for j in range(N,-1,-1):
    if dp[N][j]<10**13:
        print(j)
        break
Buggy python submission (verdict: Runtime Error):

S = str(input())
T = str(input())
a = len(S)
b = len(T)
if (a < b):
    print("UNRESTORABLE")
    exit()
m = a-b
B = "UNRESTORABLE"
for i in range(m+1):
    for j in range(b):
        if S[i+j] == T[j]:
            S =S.replace(S[i:i+b+1], T)
            S = S.replace('?', 'a')
            B = S
            break
            
            
print(B)

Fixed submission:
S = input()
T = input()
if len(S) < len(T):
    print('UNRESTORABLE')
    exit()

candidates = []
for i in range(len(S) - len(T) + 1):
    for c1,c2 in zip(S[i:i+len(T)], T):
        if c1 != '?' and c1 != c2:
            break
    else:
        cand = S[:i] + T + S[i+len(T):]
        candidates.append(cand.replace('?','a'))

if candidates:
    print(min(candidates))
else:
    print('UNRESTORABLE')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,M=map(int,input().split())
Table=[[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    Table[a-1].append(b-1)
    Table[b-1].append(a-1)
visit=[False]*N
iro=[-1]*N
kei=deque()
def nibu():
    kei.append(0)
    iro[0]=0
    while kei:
        x = kei.pop()
        visit[x]=True
        for i in Table[x]:
            if visit[i] and iro[i] == iro[x]:
                return False
            elif not visit[i]:
                kei.append(i)
                iro[i]=(iro[x]+1)%2
    return True
if nibu():
    B = iro.count(0)
    W = iro.count(1)
    ans = B*W-M
else:
    ans = (N*(N-1))//2 -M
print(ans)

Fixed submission:
from collections import deque
N,M=map(int,input().split())
Table=[[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    Table[a-1].append(b-1)
    Table[b-1].append(a-1)
visit=[False]*N
iro=[-1]*N
kei=deque()
def nibu():
    kei.append(0)
    iro[0]=0
    while kei:
        x = kei.pop()
        visit[x]=True
        for i in Table[x]:
            if visit[i] and iro[i] == iro[x]:
                return False
            elif not visit[i]:
                kei.append(i)
                iro[i]=(iro[x]+1)%2
    return True
if nibu():
    B = iro.count(0)
    W = iro.count(1)
    ans = B*W-M
else:
    ans = (N*(N-1))//2 -M
print(ans)