Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(n)]

m, d = 0, [0] * t
for a, b in sorted(ab):
  m = max(m, b+d[t-1])
  for l in range(t-1,a-1,-1):
    if(b+d[l-a] > d[l]):
      d[l] = b+d[l-a]
print(m)

Fixed submission:
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[0] * (t+1) for i in range(n+1)] for j in range(2)]
for i in range(n):
  for d in range(2):
    for l in range(1,t+1):
      if(l < a[i]):
        dp[d][i+1][l] = max(dp[d][i][l], d*(b[i]+dp[0][i][l-1]))
      else:
        dp[d][i+1][l] = max(dp[d][i][l], b[i]+dp[d][i][l-a[i]], d*(b[i]+dp[0][i][l-1]))

print(dp[1][n][t])

Buggy python submission (verdict: Runtime Error):
n, t = map(int, input().split())
d0, d1 = [0] * (t+1), [0] * (t+1)
for i in range(n):
  a, b = map(int, input().split())
  for l in range(t,a-1,-1):
    d0[l] = max(d0[l], b+d0[l-a])
    d1[l] = max(d1[l], b+d1[l-a], b+d0[l-1])
  for l in range(a-1,0,-1):
    d1[l] = max(d1[l], b+d0[l-1])
print(d1[t])

Fixed submission:
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[0] * (t+1) for i in range(n+1)] for j in range(2)]
for i in range(n):
  for d in range(2):
    for l in range(1,t+1):
      if(l < a[i]):
        dp[d][i+1][l] = max(dp[d][i][l], d*(b[i]+dp[0][i][l-1]))
      else:
        dp[d][i+1][l] = max(dp[d][i][l], b[i]+dp[d][i][l-a[i]], d*(b[i]+dp[0][i][l-1]))

print(dp[1][n][t])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 8)

n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[-1] * (t+1) for i in range(n)] for j in range(2)]
def dfs(i, l, d):
  if(i == n or l <= 0):
    return 0
  elif(dp[d][i][l] != -1):
    return dp[d][i][l]
  r = 0
  if(l > 0 and d > 0):
    r = max(r, b[i] + dfs(i+1, l - 1, d - 1))
  if(l >= a[i]):
    r = max(r, b[i] + dfs(i+1, l - a[i], d))
  r = max(r, dfs(i+1, l, d))
  dp[d][i][l] = r
  return dp[d][i][l]

print(dfs(0, t, 1))

Fixed submission:
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[0] * (t+1) for i in range(n+1)] for j in range(2)]
for i in range(n):
  for d in range(2):
    for l in range(1,t+1):
      if(l < a[i]):
        dp[d][i+1][l] = max(dp[d][i][l], d*(b[i]+dp[0][i][l-1]))
      else:
        dp[d][i+1][l] = max(dp[d][i][l], b[i]+dp[d][i][l-a[i]], d*(b[i]+dp[0][i][l-1]))

print(dp[1][n][t])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 8)

n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[-1] * (t+1) for i in range(n)] for j in range(2)]
def dfs(i, l, d):
  if(i == n or l <= 0):
    return 0
  elif(dp[d][i][l] != -1):
    return dp[d][i][l]
  r = 0
  if(l > 0 and d > 0):
    r = max(r, b[i] + dfs(i+1, l - 1, d - 1))
  if(l >= a[i]):
    r = max(r, b[i] + dfs(i+1, l - a[i], d))
  r = max(r, dfs(i+1, l, d))
  dp[d][i][l] = r
  return dp[d][i][l]

print(dfs(0, t, 1))

Fixed submission:
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[0] * (t+1) for i in range(n+1)] for j in range(2)]
for i in range(n):
  for d in range(2):
    for l in range(1,t+1):
      if(l < a[i]):
        dp[d][i+1][l] = max(dp[d][i][l], d*(b[i]+dp[0][i][l-1]))
      else:
        dp[d][i+1][l] = max(dp[d][i][l], b[i]+dp[d][i][l-a[i]], d*(b[i]+dp[0][i][l-1]))

print(dp[1][n][t])

Buggy python submission (verdict: Runtime Error):
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[-1] * (t+1) for i in [0] * n]
def dfs(i, l):
  if(i == n or l <= 0):
    return 0
  elif(dp[i][l] != -1):
    return dp[i][l]
  else:
    dp[i][l] = max(b[i] + dfs(i+1, l - a[i]), dfs(i+1, l))
    return dp[i][l]

print(dfs(0, t))

Fixed submission:
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[0] * (t+1) for i in range(n+1)] for j in range(2)]
for i in range(n):
  for d in range(2):
    for l in range(1,t+1):
      if(l < a[i]):
        dp[d][i+1][l] = max(dp[d][i][l], d*(b[i]+dp[0][i][l-1]))
      else:
        dp[d][i+1][l] = max(dp[d][i][l], b[i]+dp[d][i][l-a[i]], d*(b[i]+dp[0][i][l-1]))

print(dp[1][n][t])