Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


x,y=map(int,input().split())
s=(2*y-x)/3
t=(2*x-y)/3
if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    a = cmb(s+t, t)
    print(a%(10**9+7))

Fixed submission:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


x,y=map(int,input().split())
s=int((2*y-x)/3)
t=int((2*x-y)/3)
if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
elif s<0 or t<0:
    print(0)
else:
    a = cmb(s+t, t)
    print(a%(10**9+7))

Buggy python submission (verdict: Runtime Error):
from scipy.special import comb

x,y=map(int,input().split())
s=(2*y-x)/3
t=(2*x-y)/3
if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    a = comb(s+t, t, exact=True)
    print(a%(10**9+7))

Fixed submission:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


x,y=map(int,input().split())
s=int((2*y-x)/3)
t=int((2*x-y)/3)
if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
elif s<0 or t<0:
    print(0)
else:
    a = cmb(s+t, t)
    print(a%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())


event=[]

for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

D_list=[int(input()) for _ in range(Q)]


event.sort()
for d in D_list:
    stop_set=set()
    for e in event:
        if e[0]>d:
            break
        else :
            if e[1]==1:
                stop_set=stop_set|{e[2]}
            elif e[1]==-1:
                stop_set=stop_set-{e[2]}
    if stop_set==set():
        stop_set=stop_set|{-1}
    print(min(stop_set))

Fixed submission:
from heapq import heappop,heappush

N,Q=map(int,input().split())


event=[]
q=[]
for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

for i in range(Q):
    event.append([int(input()),2,i])

stop_set=set()
event.sort()
q=[]

for pos,m,x in event:
    if m==-1:
        stop_set.remove(x)
        
    elif m==1:
        #heappushする時点でqはソートされている
        heappush(q,x)
        stop_set.add(x)
    
    else:
        #この時点でのstop_setは、i番目の人が遭遇する通行止めの座標
        #この時点でのqは今までstopになった座標
        while q:
            #qはソート済なので、q[0]は最小値　それがstop_setから外れている場合、heappopでそれを排除する
            if q[0] not in stop_set:
                heappop(q)
            #q[0]がstop_setから外れてない場合、それ以降のqも外れていないのでbreak    
            else:
                break

        if q:
            print(q[0])
        else:
            print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#abc128
N,Q=map(int,input().split())
stop_list=[list(map(int,input().split())) for _ in range(N)]
D_list=[int(input()) for _ in range(Q)]

N_line=dict()

for i in stop_list:
    N_line[i[2]]=[]

for i in stop_list:
    N_line[i[2]].append([i[0]-0.5,i[1]-0.5])

N_line=sorted(N_line.items(), key=lambda x:x[0])
D_achieve=[]


for d in D_list:
    judge=False
    for N in N_line:
        c_number=N[0]
        #N[0]は座標、N[1]は時間のリスト
        for time in N[1]:
            if time[0]<c_number+d<time[1]:
                D_achieve.append(c_number)
                judge=True
            if judge:
                break
        if judge:
            break
    if judge==False:
        D_achieve.append(-1)

        
        
for i in D_achieve:
    print(i)

Fixed submission:
from heapq import heappop,heappush

N,Q=map(int,input().split())


event=[]
q=[]
for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

for i in range(Q):
    event.append([int(input()),2,i])

stop_set=set()
event.sort()
q=[]

for pos,m,x in event:
    if m==-1:
        stop_set.remove(x)
        
    elif m==1:
        #heappushする時点でqはソートされている
        heappush(q,x)
        stop_set.add(x)
    
    else:
        #この時点でのstop_setは、i番目の人が遭遇する通行止めの座標
        #この時点でのqは今までstopになった座標
        while q:
            #qはソート済なので、q[0]は最小値　それがstop_setから外れている場合、heappopでそれを排除する
            if q[0] not in stop_set:
                heappop(q)
            #q[0]がstop_setから外れてない場合、それ以降のqも外れていないのでbreak    
            else:
                break

        if q:
            print(q[0])
        else:
            print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
p,q,r=map(int,input().split())

    
def comb_mod(N,K,modp):

    K_fact=1
    NK_fact=1
    N_fact=1

    for i in range(1,K+1):
        K_fact*=i
    for i in range(1,N-K+1):
        NK_fact*=i
    for i in range(1,N+1):
        N_fact*=i

    K_inv=pow(K_fact, -1, modp)
    NK_inv=pow(NK_fact, -1, modp)
    pat=(N_fact*K_inv)%modp*NK_inv%modp
    return pat

pat=comb_mod(p*q-2,r-2,10**9+7)

ans=0
for i in range(0,q+1):
    ans+=i*(q-i)*p*p

for k in range(0,p+1):
    ans+=k*(p-k)*q*q


print(ans*pat%(10**9+7))

Fixed submission:
p,q,r=map(int,input().split())

    
def comb_mod(N,K,modp):

    K_fact=1
    NK_fact=1
    N_fact=1

    for i in range(1,K+1):
        K_fact*=i
        K_fact=K_fact%modp
    for i in range(1,N-K+1):
        NK_fact*=i
        NK_fact=NK_fact%modp
    for i in range(1,N+1):
        N_fact*=i
        N_fact=N_fact%modp

    K_inv=pow(K_fact, -1, modp)
    NK_inv=pow(NK_fact, -1, modp)
    pat=(N_fact*K_inv)%modp*NK_inv%modp
    return pat

pat=comb_mod(p*q-2,r-2,10**9+7)

ans=0
for i in range(0,q+1):
    ans+=i*(q-i)*p*p
    ans=ans%(10**9+7)
    
for k in range(0,p+1):
    ans+=k*(p-k)*q*q%(10**9+7)
    ans=ans%(10**9+7)

print(ans*pat%(10**9+7))
Buggy python submission (verdict: Runtime Error):
from math import gcd
N=int(input())
L=list(map(int,input().split()))
M=max(L)

def lcm(a, b):
    return a * b // gcd (a, b)

p=1
for i in L:
    p=lcm(i,p)
q=0
print(sum([(p-1)%i for i in L]))

Fixed submission:
from fractions import gcd
N=int(input())
L=list(map(int,input().split()))
M=max(L)

def lcm(a, b):
    return a * b // gcd (a, b)

p=1
for i in L:
    p=lcm(i,p)
q=0
print(sum([(p-1)%i for i in L]))
Buggy python submission (verdict: Runtime Error):
import sympy
N=int(input())
L=list(map(int,input().split()))
L_alpha=[sympy.factorint(i) for i in L]
L=[i.get(2) for i in L_alpha]
L=[0 if i==None else i for i in L ]
print(sum(L))

Fixed submission:
def two_div(n):
    count=0
    while n%2!=1:
        n=n/2
        count+=1
    return count

N=int(input())
L=list(map(int,input().split()))
L_div=[two_div(i) for i in L]
print(sum(L_div))
Buggy python submission (verdict: Time Limit Exceeded):
H=int(input())-1
K = [list(map(int, input().split())) for i in range(H)]
total_total=[]
for j in range(H):
    total=K[j][0]+K[j][1]
    for i in range(j,H-1):
        c1=K[i][0]
        s1=K[i][1]
        f1=K[i][2]
        c2=K[i+1][0]
        s2=K[i+1][1]
        f2=K[i+1][2]
        if total>s2:
            count=s2
            while total>count:
                count=count+f2
            total=count+c2
        else:
            total=s2+c2
    print(total)
print(0)

Fixed submission:
H=int(input())-1
K = [list(map(int, input().split())) for i in range(H)]
total_total=[]
for j in range(H):
    total=K[j][0]+K[j][1]
    for i in range(j,H-1):
        c1=K[i][0]
        s1=K[i][1]
        f1=K[i][2]
        c2=K[i+1][0]
        s2=K[i+1][1]
        f2=K[i+1][2]
        if total>s2:
            if (total-s2)%f2==0:
                total=total+c2
            else:
                total=((total-s2)//f2+1)*f2+s2+c2
        else:
            total=s2+c2
    print(total)
print(0)

Buggy python submission (verdict: Time Limit Exceeded):
H=int(input())-1
K = [list(map(int, input().split())) for i in range(H)]
total_total=[]
for j in range(H):
    total=K[j][0]+K[j][1]
    total_list=[total]
    for i in range(j,H-1):
        c1=K[i][0]
        s1=K[i][1]
        f1=K[i][2]
        c2=K[i+1][0]
        s2=K[i+1][1]
        f2=K[i+1][2]
        if total>s2:
            count=s2
            while total>count:
                count=count+f2
            total=count+c2
        else:
            total=s2+c2
        total_list.append(total)
    total_total.append(total_list)
for i in total_total:
    print(i[-1])
print(0)

Fixed submission:
H=int(input())-1
K = [list(map(int, input().split())) for i in range(H)]
total_total=[]
for j in range(H):
    total=K[j][0]+K[j][1]
    for i in range(j,H-1):
        c1=K[i][0]
        s1=K[i][1]
        f1=K[i][2]
        c2=K[i+1][0]
        s2=K[i+1][1]
        f2=K[i+1][2]
        if total>s2:
            if (total-s2)%f2==0:
                total=total+c2
            else:
                total=((total-s2)//f2+1)*f2+s2+c2
        else:
            total=s2+c2
    print(total)
print(0)
Buggy python submission (verdict: Runtime Error):
import itertools
N=int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]

store_str=list(product('01', repeat=10))
store=[[int(i) for i in j] for j in store_str]
store.pop(0)
all_sum=[]
for s in store:#joiの店をあけられる時間帯の組み合わせ
    value_list=[]
    for i,j in zip(F,P): #i番目の店の開いている時間帯のリスト
        l=len([1 for a,b in zip(s,i) if a==1 and b==1])
        value_list.append(j[l])
    value_sum=sum(value_list)
    all_sum.append(value_sum)
print(max(all_sum))

Fixed submission:
from itertools import product
N=int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]
store_str=list(product('01', repeat=10))
store=[[int(i) for i in j] for j in store_str]
store.pop(0)
all_sum=[]
for s in store:
    value_list=[]
    for i,j in zip(F,P): 
        l=len([1 for a,b in zip(s,i) if a==1 and b==1])
        value_list.append(j[l])
    value_sum=sum(value_list)
    all_sum.append(value_sum)
print(max(all_sum))
Buggy python submission (verdict: Runtime Error):
import numpy
N=int(input())
L = [int(input()) for i in range(N)]
print(numpy.lcm.reduce(L))

Fixed submission:
import fractions
from functools import reduce
N=int(input())
L = [int(input()) for i in range(N)]
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm(*L))
Buggy python submission (verdict: Runtime Error):
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count=count+1
print(count)

Fixed submission:
#51
Haiku = str(input())
print(Haiku.replace(","," "))

Buggy python submission (verdict: Runtime Error):
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count = count +1
print(count)

Fixed submission:
#51
Haiku = str(input())
print(Haiku.replace(","," "))
Buggy python submission (verdict: Time Limit Exceeded):
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count = count +1
print(count)

Fixed submission:
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count=count+1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
K,S=map(int, input().split())
data=[[x,y,z]for x in range(K+1)for y in range(K+1)for z in range(K+1) if x+y+z==S]
print(len(data))

Fixed submission:
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count=count+1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count = count +1
print(count)

Fixed submission:
K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count=count+1
print(count)
Buggy python submission (verdict: Runtime Error):
A = []
for _ in range(3):
    a = list(map(int, input().split()))
    A.append(a)

import numpy as np
A = np.array(A)

N = int(input())
B = []
for _ in range(N):
    B.append(int(input()))

ans = [[False] * 3 for _ in range(3)]
ans = np.array(ans)

for b in B:
    temp = (A == b)

    ans = np.logical_or(ans, temp)


if ans[0, :].all() or ans[1, :].all() or ans[2, :].all():
    print("Yes")

elif ans[:, 0].all() or ans[:, 1].all() or ans[:, 2].all():
    print("Yes")

elif ans[0, 0] and ans[1, 1] and ans[2, 2]:
    print("Yes")
elif ans[0, 2] and ans[1, 1] and ans[2, 0]:
    print("Yes")
else:
    print("No")




Fixed submission:
A = []
for _ in range(3):
    a = list(map(int, input().split()))
    A.append(a)

import numpy as np
A = np.array(A)

N = int(input())
B = []
for _ in range(N):
    B.append(int(input()))

ans = [[False] * 3 for _ in range(3)]
ans = np.array(ans)

for b in B:
    temp = (A == b)

    ans = np.logical_or(ans, temp)


if ans[0, :].all() or ans[1, :].all() or ans[2, :].all():
    print("Yes")

elif ans[:, 0].all() or ans[:, 1].all() or ans[:, 2].all():
    print("Yes")

elif ans[0, 0] and ans[1, 1] and ans[2, 2]:
    print("Yes")
elif ans[0, 2] and ans[1, 1] and ans[2, 0]:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B = map(int, input().split())

class remainder():
    def __init__(self, mod=(10**9 + 7)):
        self.mod = mod
    
    def sub(self, a, b):

        return (a + self.mod - b) % self.mod
    
    def mul(self, a, b):

        return ((a % self.mod) * (b % self.mod)) % self.mod

    def pow(self, a, b):
        bp = []
        #bp.append(1)
        bp.append(a)

        n = len(bin(b)) - 2
        for x in range(n):
            bp.append(bp[x]**2 % self.mod)

        res = 1
        for x in range(n):
            if b >> x & 1:
                res = (res * bp[x]) % self.mod
        
        return res

    def div(self, a, b):
        
        return self.mul(a, self.pow(b, self.mod - 2))

com = [0] * (B + 1)
com[0] = 1

re = remainder()

ans = re.pow(2, N) - 1
for x in range(1, B + 1):
    s = re.sub(N, x) + 1
    d = re.div(s, x)
    com[x] = re.mul(com[x - 1], d)

subA = com[A]
subB = com[B]

ans = re.sub(ans, subA)
ans = re.sub(ans, subB)

print(ans)


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

class remainder():
    def __init__(self, mod=(10**9 + 7)):
        self.mod = mod
    
    def sub(self, a, b):

        return (a + self.mod - b) % self.mod
    
    def mul(self, a, b):

        return ((a % self.mod) * (b % self.mod)) % self.mod

    def pow(self, a, b):
        bp = []
        #bp.append(1)
        bp.append(a)

        n = len(bin(b)) - 2
        for x in range(n):
            bp.append(bp[x]**2 % self.mod)

        res = 1
        for x in range(n):
            if b >> x & 1:
                #res = re.mul(res, bp[x])
                res = (res * bp[x]) % self.mod
        
        return res

    def div(self, a, b):
        
        return self.mul(a, self.pow(b, self.mod - 2))

com = [0] * (B + 1)
com[0] = 1

re = remainder()

ans = re.pow(2, N) - 1
for x in range(1, B + 1):
    s = re.sub(N, x) + 1
    d = re.div(s, x)
    com[x] = re.mul(com[x - 1], d)


subA = com[A]
subB = com[B]

ans = re.sub(ans, subA)
ans = re.sub(ans, subB)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

P = list(map(int, input().split()))

per = [ (n + 1) / 2 for  n in P]

MAX = -1
for x in range(N - K + 1):
    temp = sum(per[x : x + K])
    if MAX < temp:
        MAX = temp

print(MAX)




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

P = list(map(int, input().split()))

per = [ (n + 1) / 2 for  n in P]

m = [0] * N
m[0] = sum(per[ : K])
for x in range(1, N - K + 1):
    m[x] = m[x - 1] - per[x - 1] + per[x + K - 1]


print(max(m))
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

import math

ans = A * B / math.gcd(A, B)
print(int(ans))


Fixed submission:
A, B = map(int, input().split())
 
import fractions
 
ans = A * B / fractions.gcd(A, B)
print(int(ans))

Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

import math

ans = A * B / math.gcd(A, B)
print(int(ans))


Fixed submission:
A, B = map(int, input().split())
 
import fractions
 
ans = A * B / fractions.gcd(A, B)
print(int(ans))
Buggy python submission (verdict: Runtime Error):
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N

def DFS(x, pre, cnt):
    if C[x] < cnt:
        C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        if a == (U - 1):
            C[a] = cnt
            continue:
        
        DFS(a, x, cnt)


DFS(V - 1, -1, 0)
ans = max(C) - 1
if ans < 0:
    ans = 0
print(ans)


Fixed submission:
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
import numpy as np
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)

E = np.array(C) > np.array(D)
C = np.array(C)
ans = max(C[E]) - 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

M = [set() for _ in range(N)]

A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    A[a - 1].append((b - 1, i))
    A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
    cnt = 1
    for a in A[x]:
        if a[0] == pre:
            continue

        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

print(max(ans))
for a in ans:
    print(a)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
N = int(input())

M = [set() for _ in range(N)]

A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    A[a - 1].append((b - 1, i))
    A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
    cnt = 1
    for a in A[x]:
        if a[0] == pre:
            continue

        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

print(max(ans))
for a in ans:
    print(a)

Buggy python submission (verdict: Runtime Error):
N = int(input())

M = [set() for _ in range(N)]

A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    A[a - 1].append((b - 1, i))
    A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
    for a in A[x]:
        if a[0] == pre:
            continue

        cnt = 1
        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

print(max(ans))
for a in ans:
    print(a)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
N = int(input())

M = [set() for _ in range(N)]

A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    A[a - 1].append((b - 1, i))
    A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
    cnt = 1
    for a in A[x]:
        if a[0] == pre:
            continue

        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

print(max(ans))
for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N, T = map(int, input().split())

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

dp1 = [[0] * (T) for _ in range(N + 1)]

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)

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

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

dp1 = [[0] * (T) for _ in range(N + 1)]

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)