Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

def gcd(n,m,l):
    A = [ n , m , l ]
    A = sorted(A)
    
    while A[0] % A[2] != 0 :
        A[0] , A[2] = A[2] , A[0] % A[2]

    while A[1] % A[2] != 0 :
        A[1] , A[2] = A[2] , A[1] % A[2]
    
    return A[2]
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )
    



Fixed submission:
K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

def gcd(n,m):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    return m
  
S = 0


for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            d = gcd(a,b)
            S += gcd(c,d)

print ( S )
    


Fixed submission:
K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )
    

Fixed submission:
K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )
Buggy python submission (verdict: Runtime Error):
x, y, z=int(input(),input(),input())
x,y=y,x
x,z=z,x
print(str(x) + " " + str(y) + " " + str(z) )

Fixed submission:
x, y, z = map(int, input().split())

print ( str(z) + " " + str(x) + " " + str(y) )
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = [int(i) for i in input().split()]

S = 0

for k in range (0 , N):
	S += A[k]

for j in range (0 , N):
  	m = 0
  	if A[j] >= S / ( 4 * M ):
    	m = m + 1
    
if m >= M:
  	print ( "Yes" )
else:
 	print ( "No" ) 
    

Fixed submission:
N, M = map(int, input().split())
A = [int(i) for i in input().split()]

S = 0

for k in range (0 , N):
	S += A[k]

m = 0
for j in range (0 , N):
	if A[j] >= (S / ( 4 * M )):
		m = m + 1

if m >= M:
  	print ( "Yes" )
else:
 	print ( "No" )
Buggy python submission (verdict: Runtime Error):
N, K = input().split()

if N >= K:
	N %= K

if ( K / 2 ) >= N:
	print ( N )

else:
    print ( K - N )

Fixed submission:
N, K = map(int,input().split())
 
if N >= K:
	N %= K
 
if ( K // 2 ) >= N:
	print ( N )
 
else:
    print ( K - N )
Buggy python submission (verdict: Runtime Error):
N = int(inout())
L = input().split()
flag = 0

for i in range(N):
  L[i] = int(L[i])
  total += L[i]

for i in range(N):
  if L[i]*2 >= total:
    print("No")
    flag = 1
    break

if flag == 0:
  print("Yes")


Fixed submission:
N = int(input())
L = input().split()
max = 0
count = 0

for i in range(N):
  count += int(L[i])
  if max < int(L[i]):
    max = int(L[i])
    
if count > 2*max:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
N = int(inout())
L = int(input().split())
flag = 0

for i in range(N):
  total += L[i]

for i in range(N):
  if L[i]*2 >= total:
    print("No")
    flag = 1
    break

if flag == 0:
  print("Yes")


Fixed submission:
N = int(input())
L = input().split()
max = 0
count = 0

for i in range(N):
  count += int(L[i])
  if max < int(L[i]):
    max = int(L[i])
    
if count > 2*max:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
N = int(inout())
L = int(input().split())
flag = 0

for i in range(N):
  total += L[i]

for i in range(N):
  if A[i]*2 >= total:
    print("No")
    flag = 1
    break

if flag == 0:
  print("Yes")

Fixed submission:
N = int(input())
L = input().split()
max = 0
count = 0

for i in range(N):
  count += int(L[i])
  if max < int(L[i]):
    max = int(L[i])
    
if count > 2*max:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
L = map(int,input().split())
max = 0
count = 0

for i in range(N):
  count += L[i]
  if max < L[i]:
    max = L[i]
    
if count < 2*max:
  print("Yes")
else:
  print("No")
  

Fixed submission:
N = int(input())
L = input().split()
max = 0
count = 0

for i in range(N):
  count += int(L[i])
  if max < int(L[i]):
    max = int(L[i])
    
if count > 2*max:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())

Ch += 1
Cw += 1
Dh += 1
Dw += 1

S = [["#" for _ in range(W + 4)] for _ in range(2)]
for _ in range(H):
    S.append(["#"] * 2 + list(input()) + ["#"] * 2)
S.append(["#" for _ in range(W + 4)])
S.append(["#" for _ in range(W + 4)])

cnt = [[float("inf")] * (W + 4) for _ in range(H + 4)]
cnt[Ch][Cw] = 0

DX = [0, 0, -1, 1]
DY = [-1, 1, 0, 0]

from collections import deque

def serch(Sh, Sw, count):
    q = [(Sh, Sw)]
    done = [(Sh, Sw)]
    while q:
        qq = []
        for h, w in q:
            for dy, dx in zip(DY, DX):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > count:
                    qq.append((nh, nw))
                    done.append((nh, nw))
                    cnt[nh][nw] = count
        q = qq
    
    return done

DONE = serch(Ch, Cw, 0)
ans = 1
while DONE:
    DDONE = []
    for h, w in DONE:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > ans:
                    cnt[nh][nw] = ans
                    DDONE += serch(nh, nw, ans)
    
    ans += 1
    DONE = DDONE

if cnt[Dh][Dw] == float("inf"):
    print(-1)
else:
    print(cnt[Dh][Dw])

Fixed submission:
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())

Ch += 1
Cw += 1
Dh += 1
Dw += 1

S = [["#" for _ in range(W + 4)] for _ in range(2)]
for _ in range(H):
    S.append(["#"] * 2 + list(input()) + ["#"] * 2)
S.append(["#" for _ in range(W + 4)])
S.append(["#" for _ in range(W + 4)])

cnt = [[float("inf")] * (W + 4) for _ in range(H + 4)]
cnt[Ch][Cw] = 0

DX = [0, 0, -1, 1]
DY = [-1, 1, 0, 0]

from collections import deque

def serch(Sh, Sw, count):
    q = [(Sh, Sw)]
    done = [(Sh, Sw)]
    while q:
        qq = []
        for h, w in q:
            for dy, dx in zip(DY, DX):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > count:
                    qq.append((nh, nw))
                    done.append((nh, nw))
                    cnt[nh][nw] = count
        q = qq
    
    return done

DONE = serch(Ch, Cw, 0)
ans = 1
while DONE:
    DDONE = []
    for h, w in DONE:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                nh = h + dy
                nw = w + dx

                if S[nh][nw] == "." and cnt[nh][nw] > ans:
                    cnt[nh][nw] = ans
                    DDONE += serch(nh, nw, ans)
    
    ans += 1
    DONE = DDONE

if cnt[Dh][Dw] == float("inf"):
    print(-1)
else:
    print(cnt[Dh][Dw])
Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree(object):
    """
    セグメントツリー (0-indexed)

    1. 値の更新 O(logN)
    2. 区間クエリ O(logN)
    """
    def __BinOp(self, x, y):
        """ セグ木で使用する二項演算 """
        return x + y

    def __init__(self, init_ele, N:int):
        """
        セグ木を構築する

        init_ele: 単位元 
        N: 要素数
        """
        self.__init_ele = init_ele
        self.__n = 1
        while self.__n < N:
            self.__n <<= 1

        self.__dat = [init_ele] * (2 * self.__n)
    
    def update(self, k:int, x):
        """ k番目の値をxに変更する """
        k += self.__n - 1
        self.__dat[k] = x
        while k:
            k = (k - 1) // 2
            self.__dat[k] = self.__BinOp(
                self.__dat[k * 2 + 1], self.__dat[k * 2 + 2]
                )
    
    def query(self, p:int, q:int):
        """ 区間クエリ [p,q) """
        if q <= p: return self.__init_ele
        p += self.__n - 1
        q += self.__n - 2
        res = self.__init_ele
        while q - p > 1:
            if not (p & 1):
                res = self.__BinOp(res, self.__dat[p])
            if q & 1:
                res = self.__BinOp(res, self.__dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self.__BinOp(res, self.__dat[p])
        if p != q: res = self.__BinOp(res, self.__dat[q])
        return res
    
    def get_num(self, k:int):
        """ k番目の値を取得する """
        k += self.__n - 1
        return self.__dat[k]

N = int(input())
S = input()

R = SegmentTree(0, N)
G = SegmentTree(0, N)
B = SegmentTree(0, N)

for i in range(N):
    if S[i] == "R":
        R.update(i, 1)
    elif S[i] == "G":
        G.update(i, 1)
    else:
        B.update(i, 1)

ans = 0
for i in range(N):
    for j in range(i + 1, N - 1):
        if S[i] == S[j]: continue
        tmp = set(["R","G","B"])
        tmp.remove(S[i])
        tmp.remove(S[j])
        Sk = tmp.pop()
        no = j + (j - i)
        if Sk == "R":
            ans += R.query(j + 1, min(N, no)) + R.query(min(N, no + 1), N)
        elif Sk == "G":
            ans += G.query(j + 1, min(N, no)) + G.query(min(N, no + 1), N)
        else:
            ans += B.query(j + 1, min(N, no)) + B.query(min(N, no + 1), N)

print(ans)

Fixed submission:
N = int(input())
S = input()

R = [0] * N
G = [0] * N
B = [0] * N

for i in range(N):
    if S[i] == "R":
        R[i] += 1
    elif S[i] == "G":
        G[i] += 1
    else:
        B[i] += 1

from itertools import accumulate

R = [0] + list(accumulate(R))
G = [0] +list(accumulate(G))
B = [0] + list(accumulate(B))

ans = 0
for i in range(N):
    for j in range(i + 1, N - 1):
        if S[i] == S[j]: continue
        tmp = set(["R","G","B"])
        tmp.remove(S[i])
        tmp.remove(S[j])
        Sk = tmp.pop()
        no = j + (j - i)
        if Sk == "R":
            ans += R[min(N, no)] - R[j] + R[N] - R[min(N, no + 1)]
        elif Sk == "G":
            ans += G[min(N, no)] - G[j] + G[N] - G[min(N, no + 1)]
        else:
            ans += B[min(N, no)] - B[j] + B[N] - B[min(N, no + 1)]

print(ans)
Buggy python submission (verdict: Runtime Error):
X= int(input())
ans = X // 500 * 1000
X -= X // 500 * 
ans += (X // 5) * 5
print(ans)

Fixed submission:
X = int(input())

ans = 0

num = X // 500
X -= 500 * num
ans += num * 1000

num = X // 5
ans += num * 5

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

flag = False
for _ in range(Q):
    IN = list(map(str,input().split()))

    if IN[0] == "1":
        flag = not flag
        continue

    _,F,C = IN
    if flag:
        if F == "1":
            S += C
        else:
            S = C + S
    else:
        if F == "1":
            S = C + S
        else:
            S += C

if flag:
    print(S[::-1])
else:
    print(S)

Fixed submission:
from collections import deque
S = deque(list(input()))
Q = int(input())

flag = False
for _ in range(Q):
    IN = list(map(str,input().split()))

    if IN[0] == "1":
        flag = not flag
        continue

    _,F,C = IN
    if flag:
        if F == "1":
            S.append(C)
        else:
            S.appendleft(C)
    else:
        if F == "1":
            S.appendleft(C)
        else:
            S.append(C)

if flag:
    print(*reversed(S),sep="")
else:
    print(*S,sep="")

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

for _ in range(Q):
    IN = list(map(str,input().split()))
    if IN[0] == "1":
        S = S[::-1]
        continue
    _,F,C = IN
    if F == "1":
        S = C + S
    else:
        S += C

print(S)

Fixed submission:
from collections import deque
S = deque(list(input()))
Q = int(input())

flag = False
for _ in range(Q):
    IN = list(map(str,input().split()))

    if IN[0] == "1":
        flag = not flag
        continue

    _,F,C = IN
    if flag:
        if F == "1":
            S.append(C)
        else:
            S.appendleft(C)
    else:
        if F == "1":
            S.appendleft(C)
        else:
            S.append(C)

if flag:
    print(*reversed(S),sep="")
else:
    print(*S,sep="")
Buggy python submission (verdict: Time Limit Exceeded):
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P

r1,c1,r2,c2 = map(int,input().split())
MOD = 10**9 + 7
ans = 0

C = Combination(r2+c2+2, MOD)

ans += C.getComb(r2+c2+2, r2+1)
ans -= C.getComb(r2+c1+1, r2+1)
ans -= C.getComb(r1+c2+1, r1)
ans += C.getComb(r1+c1, r1)

print(ans % MOD)

Fixed submission:
def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    # n!/(n-k)!
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    # k!
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    # n!/((n-k)!*k!)
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

r1,c1,r2,c2 = map(int,input().split())
MOD = 10**9 + 7
ans = 0

ans += getComb(r2+c2+2, r2+1, MOD)
ans -= getComb(r2+c1+1, r2+1, MOD)
ans -= getComb(r1+c2+1, r1, MOD)
ans += getComb(r1+c1, r1, MOD)

print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
H,N = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

# dp[i]: 体力iにするための最小魔力
dp = [float("inf")] * (H + 1)

# 初期条件
dp[H] = 0

for i in range(H, -1, -1):
    for a, b in AB:
        HP = max(0, i - a)
        dp[HP] = min(dp[HP], dp[i] + b)

print(dp[0])

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    H,N = map(int,input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [float("inf")] * (H+1)

    dp[H] = 0

    for i in range(H,-1,-1):
        for j in range(N):
            tmp = max(0,i-AB[j][0])
            dp[tmp] = min(dp[tmp], dp[i]+AB[j][1])

    print(dp[0])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    H,N = map(int,input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [float("inf")] * (H+1)

    dp[H] = 0

    for i in range(H,-1,-1):
        for j in range(N):
            tmp = max(0,i-AB[j][0])
            dp[tmp] = min(dp[tmp], dp[i]+AB[j][1])

    print(dp[0])

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    H,N = map(int,input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [float("inf")] * (H+1)

    dp[H] = 0

    for i in range(H,-1,-1):
        for j in range(N):
            tmp = max(0,i-AB[j][0])
            dp[tmp] = min(dp[tmp], dp[i]+AB[j][1])

    print(dp[0])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

N = int(input())
S = tuple(input())

from collections import deque

ans = 0

# Rnum: 000 ~ 999
for Rnum in range(0,1000):
    R = deque(str(Rnum).zfill(3))

    for s in S:
        if s == R[0]:
            R.popleft()
        if not R:
            ans += 1
            break

print(ans)

Fixed submission:
N = int(input())
S = list(input())

def my_index(LIST, VALUE,START):
    if VALUE in LIST[START:]:
        return LIST.index(VALUE,START)
    else:
        return float("inf")

answer = 0
# 暗証番号がiとなるか判定
for i in range(1000):
    PIN = str(i).rjust(3,"0")
    if PIN[0] in S:
        one_digit = S.index(PIN[0])
    else:
        continue
    if PIN[1] in S:
        two_digit = my_index(S,PIN[1],one_digit+1)
        if two_digit == float("inf"):
            continue
    else:
        continue
    if PIN[2] in S:
        three_digit = my_index(S,PIN[2],two_digit+1)
        if three_digit == float("inf"):
            continue
    else:
        continue
    answer += 1

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

N = int(input())
S = [int(i) for i in list(input())]

answer = defaultdict(int)

for a in range(N-2):
    for b in range(a+1,N-1):
        for c in range(b+1,N):
            num = S[a]*100 + S[b]*10 + S[c]
            answer[num] += 1

print(len(answer))

Fixed submission:
N = int(input())
S = list(input())

def my_index(LIST, VALUE,START):
    if VALUE in LIST[START:]:
        return LIST.index(VALUE,START)
    else:
        return float("inf")

answer = 0
# 暗証番号がiとなるか判定
for i in range(1000):
    PIN = str(i).rjust(3,"0")
    if PIN[0] in S:
        one_digit = S.index(PIN[0])
    else:
        continue
    if PIN[1] in S:
        two_digit = my_index(S,PIN[1],one_digit+1)
        if two_digit == float("inf"):
            continue
    else:
        continue
    if PIN[2] in S:
        three_digit = my_index(S,PIN[2],two_digit+1)
        if three_digit == float("inf"):
            continue
    else:
        continue
    answer += 1

print(answer)
Buggy python submission (verdict: Runtime Error):
S = input()

week = ["SUN","MOM","TUE","WED","THU","FRI","SAT"]

print(len(week)-week.index(S))

Fixed submission:
S = input()

week = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

print(len(week)-week.index(S))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
S = np.cumsum(A)

answer = 0
for j in range(N):
    for i in range(j+1,min(N+1, K+j)):
        if (S[i]- S[j]) % K == (i-j):
            answer += 1

print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + [int(i)-1 for i in input().split()]
Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

counter = defaultdict(int)
answer = 0
for i,x in enumerate(Acum):
    answer += counter[x]
    counter[x] += 1
    if i-K+1 >= 0:
        counter[Acum[i-K+1]] -= 1
  
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N,T = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort()

# dp[i][j]: 満足度の最大値
# i: i品目まで
# j: 制限時間(< T)
dp = [[0] * 3100 for _ in range(3100)]

dp[0][0] = 0

# 貰うDP
ans = 0
for i in range(1, N + 1):
    for j in range(T):
        dp[i][j] = dp[i - 1][j]
        
        # ラストオーダーはAB[i - 1]
        ans = max(ans, dp[i][j] + AB[i - 1][1])

        if j - AB[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

print(ans)

Fixed submission:
def main():
    N,T = map(int, input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    AB.sort()

    # dp[i][j]: 満足度の最大値
    # i: i品目まで
    # j: 制限時間(< T)
    dp = [[0] * 3100 for _ in range(3100)]

    dp[0][0] = 0

    # 貰うDP
    ans = 0
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]
            
            # ラストオーダーはAB[i - 1]
            ans = max(ans, dp[i][j] + AB[i - 1][1])

            if j - AB[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

    print(ans)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N,T = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort(key=lambda x: (x[0],x[1]))

# dp[i][j]: 満足度の最大値
# i: i品目まで
# j: 制限時間(< T)
dp = [[0] * 3100 for _ in range(3100)]

dp[0][0] = 0

# 貰うDP
ans = 0
for i in range(1, N + 1):
    for j in range(T):
        dp[i][j] = dp[i - 1][j]
        
        # ラストオーダーはAB[i - 1]
        ans = max(ans, dp[i][j] + AB[i - 1][1])

        if j - AB[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

print(ans)

Fixed submission:
def main():
    N,T = map(int, input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    AB.sort()

    # dp[i][j]: 満足度の最大値
    # i: i品目まで
    # j: 制限時間(< T)
    dp = [[0] * 3100 for _ in range(3100)]

    dp[0][0] = 0

    # 貰うDP
    ans = 0
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]
            
            # ラストオーダーはAB[i - 1]
            ans = max(ans, dp[i][j] + AB[i - 1][1])

            if j - AB[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

    print(ans)

if __name__ == "__main__":
    main()