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

from collections import defaultdict
dp0 = defaultdict(lambda: 0)
dp1 = defaultdict(lambda: 0)
dp0[0] = 0
dp1[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    _dp0 = defaultdict(lambda: 0)
    _dp1 = defaultdict(lambda: 0)
    for k0,v0 in dp0.items():
        _dp0[k0] = max(_dp0[k0], v0)
        if k0+a < T:
            _dp0[k0+a] = max(_dp0[k0+a], v0+b)
        _dp1[k0] = max(_dp1[k0], v0+b)
    for k1,v1 in dp1.items():
        _dp1[k1] = max(_dp1[k1], v1)
        if k1+a < T:
            _dp1[k1+a] = max(_dp1[k1+a], v1+b)
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

from collections import defaultdict
dp0 = defaultdict(lambda: 0)
dp1 = defaultdict(lambda: 0)
dp0[0] = 0
dp1[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    _dp0 = defaultdict(lambda: 0)
    _dp1 = defaultdict(lambda: 0)
    for k0,v0 in dp0.items():
        _dp0[k0] = max(_dp0[k0], v0)
        if k0+a < T:
            _dp0[k0+a] = max(_dp0[k0+a], v0+b)
        _dp1[k0] = max(_dp1[k0], v0+b)
    for k1,v1 in dp1.items():
        _dp1[k1] = max(_dp1[k1], v1)
        if k1+a < T:
            _dp1[k1+a] = max(_dp1[k1+a], v1+b)
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

from collections import defaultdict
dp0 = defaultdict(lambda: 0)
dp1 = defaultdict(lambda: 0)
dp0[0] = 0
dp1[0] = 0

for i,(a,b) in enumerate(AB):
    _dp0 = defaultdict(lambda: 0)
    _dp1 = defaultdict(lambda: 0)
    for k0,v0 in dp0.items():
        _dp0[k0] = max(_dp0[k0], v0)
        if k0+a < T:
            _dp0[k0+a] = max(_dp0[k0+a], v0+b)
        _dp1[k0] = max(_dp1[k0], v0+b)
    for k1,v1 in dp1.items():
        _dp1[k1] = max(_dp1[k1], v1)
        if k1+a < T:
            _dp1[k1+a] = max(_dp1[k1+a], v1+b)
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp0 = [{0:0} for i in range(N+1)]
dp1 = [{0:0} for i in range(N+1)]

for i,(a,b) in enumerate(AB):
    for k0,v0 in dp0[i].items():
        if k0 in dp0[i+1]:
            dp0[i+1][k0] = max(dp0[i+1][k0], v0)
        else:
            dp0[i+1][k0] = v0
        if k0+a < T:
            if k0+a in dp0[i+1]:
                dp0[i+1][k0+a] = max(dp0[i+1][k0+a], v0+b)
            else:
                dp0[i+1][k0+a] = v0+b
        if k0 in dp1[i+1]:
            dp1[i+1][k0] = max(dp1[i+1][k0], v0+b)
        else:
            dp1[i+1][k0] = v0+b
    for k1,v1 in dp1[i].items():
        if k1 in dp1[i+1]:
            dp1[i+1][k1] = max(dp1[i+1][k1], v1)
        else:
            dp1[i+1][k1] = v1
        if k1+a < T:
            if k1+a in dp1[i+1]:
                dp1[i+1][k1+a] = max(dp1[i+1][k1+a], v1+b)
            else:
                dp1[i+1][k1+a] = v1+b

print(max(dp1[-1].values()))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
maxt = 0
for i,(a,b) in enumerate(AB):
    maxt = min(T-1, maxt + a)
    for t in range(maxt, -1,-1):
        for k in range(2):
            dpitk = dp[i][t][k]
            if dpitk < 0: continue
            if dp[i+1][t][k] < dpitk: dp[i+1][t][k] = dpitk
            if t+a < T:
                if dp[i+1][t+a][k] < dpitk + b: dp[i+1][t+a][k] = dpitk + b
            if k==0:
                if dp[i+1][t][1] < dpitk + b: dp[i+1][t][1] = dpitk + b
print(max(a[1] for a in dp[-1]))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
maxt = 0
for i,(a,b) in enumerate(AB):
    maxt = min(T-1, maxt + a)
    for t in range(maxt, -1,-1):
        for k in range(2):
            dpitk = dp[i][t][k]
            if dpitk < 0: continue
            if dp[i+1][t][k] < dpitk: dp[i+1][t][k] = dpitk
            if t+a < T:
                if dp[i+1][t+a][k] < dpitk + b: dp[i+1][t+a][k] = dpitk + b
            if k==0:
                if dp[i+1][t][1] < dpitk + b: dp[i+1][t][1] = dpitk + b
print(max(a[1] for a in dp[-1]))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
for i,(a,b) in enumerate(AB):
    for t in range(T-1,-1,-1):
        for k in range(2):
            dpitk = dp[i][t][k]
            if dpitk < 0: continue
            if dp[i+1][t][k] < dpitk: dp[i+1][t][k] = dpitk
            if t+a < T:
                if dp[i+1][t+a][k] < dpitk + b: dp[i+1][t+a][k] = dpitk + b
            if k==0:
                if dp[i+1][t][1] < dpitk + b: dp[i+1][t][1] = dpitk + b
print(max(a[1] for a in dp[-1]))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
for i,(a,b) in enumerate(AB):
    for t in range(T-1,-1,-1):
        for k in range(2):
            if dp[i][t][k] < 0: continue
            if dp[i+1][t][k] < dp[i][t][k]: dp[i+1][t][k] = dp[i][t][k]
            if t+a < T:
                if dp[i+1][t+a][k] < dp[i][t][k] + b: dp[i+1][t+a][k] = dp[i][t][k] + b
            if k==0:
                if dp[i+1][t][1] < dp[i][t][0] + b: dp[i+1][t][1] = dp[i][t][0] + b
print(max(a[1] for a in dp[-1]))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp = [[[0,0] for t in range(T)] for i in range(N+1)]
for i,(a,b) in enumerate(AB):
    for t in range(T-1,-1,-1):
        if dp[i+1][t][0] < dp[i][t][0]: dp[i+1][t][0] = dp[i][t][0]
        if dp[i+1][t][1] < dp[i][t][1]: dp[i+1][t][1] = dp[i][t][1]
        if t+a < T:
            if dp[i+1][t+a][0] < dp[i][t][0] + b: dp[i+1][t+a][0] = dp[i][t][0] + b
            if dp[i+1][t+a][1] < dp[i][t][1] + b: dp[i+1][t+a][1] = dp[i][t][1] + b
        if dp[i+1][t][1] < dp[i][t][0] + b: dp[i+1][t][1] = dp[i][t][0] + b
print(dp[-1][-1][-1])

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

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

dp = [[[0,0] for t in range(T)] for i in range(N+1)]
for i,(a,b) in enumerate(AB):
    for t in range(T-1,-1,-1):
        dp[i+1][t][0] = max(dp[i+1][t][0], dp[i][t][0])
        dp[i+1][t][1] = max(dp[i+1][t][1], dp[i][t][1])
        if t+a < T:
            dp[i+1][t+a][0] = max(dp[i+1][t+a][0], dp[i][t][0] + b)
            dp[i+1][t+a][1] = max(dp[i+1][t+a][1], dp[i][t][1] + b)
        dp[i+1][t][1] = max(dp[i+1][t][1], dp[i][t][0] + b)
print(dp[-1][-1][-1])

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))