Buggy python submission (verdict: Runtime Error):
dp = [[-1 for i in range(6005)] for j in range(6005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
data = []
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    data.append([a,b])
    A.append(a)
    B.append(b)

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

print(f(0, 0))


Fixed submission:
dp = [[-1 for i in range(6005)] for j in range(6005)]


def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
data = []
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    data.append([a,b])
    A.append(a)
    B.append(b)

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

for idx in range(N, -1, -1):
    for time in range(T, -1, -1):
        if time == T:
            dp[idx][time] = 0
            continue
        if idx == N:
            dp[idx][time] = 0
            continue
        if A[idx]+time >= T:
            fval = 0
        else:
            fval = dp[idx+1][time+A[idx]]
        dp[idx][time] = max(dp[idx+1][time], B[idx] + fval)

print(dp[0][0])

Buggy python submission (verdict: Runtime Error):
dp = [[-1 for i in range(6005)] for j in range(6005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    A.append(a)
    B.append(b)

print(f(0, 0))


Fixed submission:
dp = [[-1 for i in range(6005)] for j in range(6005)]


def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
data = []
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    data.append([a,b])
    A.append(a)
    B.append(b)

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

for idx in range(N, -1, -1):
    for time in range(T, -1, -1):
        if time == T:
            dp[idx][time] = 0
            continue
        if idx == N:
            dp[idx][time] = 0
            continue
        if A[idx]+time >= T:
            fval = 0
        else:
            fval = dp[idx+1][time+A[idx]]
        dp[idx][time] = max(dp[idx+1][time], B[idx] + fval)

print(dp[0][0])

Buggy python submission (verdict: Runtime Error):
dp = [[-1 for i in range(3005)] for j in range(3005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    A.append(a)
    B.append(b)

print(f(0, 0))


Fixed submission:
dp = [[-1 for i in range(6005)] for j in range(6005)]


def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
data = []
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    data.append([a,b])
    A.append(a)
    B.append(b)

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

for idx in range(N, -1, -1):
    for time in range(T, -1, -1):
        if time == T:
            dp[idx][time] = 0
            continue
        if idx == N:
            dp[idx][time] = 0
            continue
        if A[idx]+time >= T:
            fval = 0
        else:
            fval = dp[idx+1][time+A[idx]]
        dp[idx][time] = max(dp[idx+1][time], B[idx] + fval)

print(dp[0][0])