Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(5000)
input = sys.stdin.readline

TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [(-1, -1)]
for i in range(1, N + 1):
    time_value.append(tuple(int(a) for a in input().split()))

# Sort the array in the increasing order of value
time_value.sort(key = lambda x:x[VAL])


# table for knapsack problem
# maximum possible time is T-1
dp_table = {}

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif (n, t) in dp_table:
        return dp_table[(n, t)]
    elif time_value[n][TIME] > t:
        ans = knapsack(n - 1, t)
    else:
        ans = max(knapsack(n - 1, t),
                  time_value[n][VAL] + knapsack(n - 1, t - time_value[n][TIME]))

    dp_table[(n, t)] = ans
    return ans

def all_you_can_eat(N, T):
    val_acum = time_value[N][VAL]
    t = T - 1
    max_val = val_acum + knapsack(N - 1, t)

    for n in range(N - 1, 0, -1):  # food to eat at the end
        val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
        t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
        if t < 0: break
        tmp = val_acum + knapsack(n - 1, t)
        max_val = max(max_val, tmp)

    return max_val

print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = {}

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif (n, t) in dp_table:
        return dp_table[(n, t)]
    elif time[n] > t:
        ans = knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[(n, t)] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

# Fill in dp_table
def knapsack():

    for t in range(0, T):
        dp_table[0, t] = 0

    for n in range(1, N + 1):
        dp_table[n, 0] = 0
        for t in range(1, T):
            if time[n] > t:
                dp_table[n, t] = dp_table[n - 1, t]
            else:
                dp_table[n, t] = max(dp_table[n - 1, t], value[n] + dp_table[n - 1, t - time[n]])

    return None


def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + dp_table[n - 1, t - 1]
        return max(tmp1, tmp2)

knapsack()
print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif dp_table[n, t] >= 0:
        return dp_table[n, t]
    elif time[n] > t:
        ans = knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[n, t] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(3000)

import numpy as np
N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif dp_table[n, t] >= 0:
        return dp_table[n, t]
    elif time[n] > t:
        ans = knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[n, t] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

Buggy python submission (verdict: Runtime Error):
import numpy as np
N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif dp_table[n, t] >= 0:
        return dp_table[n, t]
    elif time[n] > t:
        ans = knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[n, t] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

Buggy python submission (verdict: Runtime Error):
import numpy as np
N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1)
value = np.full(N + 1, -1)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1)

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif dp_table[n, t] >= 0:
        return dp_table[n, t]
    elif time[n] > t:
        ans =  knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[n, t] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)