Problem:
 Score : 500 points    Problem Statement Takahashi is at an all-you-can-eat restaurant.  The restaurant offers N kinds of dishes. It takes A_i minutes to eat the i -th dish, whose deliciousness is B_i .  The restaurant has the following rules:   You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.  You cannot order the same kind of dish more than once.  Until you finish eating the dish already served, you cannot order a new dish.  After T-0.5 minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.   Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.  What is the maximum possible happiness achieved by making optimal choices?      Constraints  2 \leq N \leq 3000  1 \leq T \leq 3000  1 \leq A_i \leq 3000  1 \leq B_i \leq 3000  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  T  A_1  B_1  :  A_N  B_N       Output Print the maximum possible happiness Takahashi can achieve.        Sample Input 1 2 60
10 10
100 100      Sample Output 1 110  By ordering the first and second dishes in this order, Takahashi's happiness will be 110 .  Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.       Sample Input 2 3 60
10 10
10 20
10 30      Sample Output 2 60  Takahashi can eat all the dishes within 60 minutes.       Sample Input 3 3 60
30 10
30 20
30 30      Sample Output 3 50  By ordering the second and third dishes in this order, Takahashi's happiness will be 50 .  We cannot order three dishes, in whatever order we place them.       Sample Input 4 10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25      Sample Output 4 145

Solution (Python):
N, T = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(N)]
D.sort()
dp = [[0] * T for _ in range(N + 1)]

for i in range(N):
    A, B = D[i]
    for j in range(T):
        here = dp[i][j]
        if j < A:
            dp[i + 1][j] = here
        else:
            dp[i + 1][j] = max(here, dp[i][j - A] + B)

t = 0
ans = 0
for i in range(N - 1, -1, -1):
    ans = max(ans, dp[i + 1][T - 1] + t)
    t = max(t, D[i][1])

print(ans)

Solution (Python):
N, T = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(N)]
D.sort()
dp = [[0] * T for _ in range(N + 1)]

for i in range(N):
    A, B = D[i]
    for j in range(T):
        here = dp[i][j]
        if j < A:
            dp[i + 1][j] = here
        else:
            dp[i + 1][j] = max(here, dp[i][j - A] + B)

maxB = [0] * (N + 1)
t = 0
for i in range(N - 1, -1, -1):
    t = max(t, D[i][1])
    maxB[i] = t

ans = 0
for i in range(N):
    ans = max(ans, dp[i + 1][T - 1] + maxB[i + 1])

print(ans)

Solution (Python):
import sys

N, T = map(int, input().split())
S = sys.stdin.readlines()
A = []
B = []
for s in S:
    a, b = map(int, s.split())
    A.append(a)
    B.append(b)

dp1 = [[0] * T for _ in range(N + 1)]
for i in range(N):
    for j in range(T):
        here = dp1[i][j]
        if j < A[i]:
            dp1[i + 1][j] = here
        else:
            dp1[i + 1][j] = max(here, dp1[i][j - A[i]] + B[i])

dp2 = [[0] * T for _ in range(N + 2)]
for i in range(N, 0, -1):
    for j in range(T):
        here = dp2[i + 1][j]
        if j < A[i - 1]:
            dp2[i][j] = here
        else:
            dp2[i][j] = max(here, dp2[i + 1][j - A[i - 1]] + B[i - 1])

ans = 0
for i in range(1, N + 1):
    t = 0
    for j in range(T):
        t2 = dp1[i - 1][j] + dp2[i + 1][T - 1 - j]
        t = max(t, t2)
    ans = max(ans, t + B[i - 1])

print(ans)

Solution (Python):
N,T = list(map(int,input().split()))

A =[list(map(int,input().split())) for i in range(N)]

A.sort(key = lambda x:x[0])

INF = float("inf")

DP = [[-INF]*(T+3001) for i in range(N+1)]

DP[0][0] = 0

for i in range(N):
    for j in range(T):
        DP[i+1][j] = max(DP[i+1][j],DP[i][j])
        DP[i+1][j+A[i][0]] = max(DP[i+1][j+A[i][0]],DP[i][j+A[i][0]],DP[i][j]+A[i][1])
score = 0
for i in range(N):
    for j in range(T+A[i][0]):
        score = DP[i+1][j] if DP[i+1][j]>score else score

print(score)

Solution (Python):
N,T = list(map(int,input().split()))

A =[list(map(int,input().split())) for i in range(N)]

A.sort(key = lambda x:x[0])

INF = float("inf")

DP = [[-INF]*(T+3001) for i in range(N+1)]

DP[0][0] = 0

for i in range(N):
    for j in range(T):
        DP[i+1][j] = max(DP[i+1][j],DP[i][j])
        DP[i+1][j+A[i][0]] = max(DP[i+1][j+A[i][0]],DP[i][j+A[i][0]],DP[i][j]+A[i][1])
score = 0
for i in range(N):
    for j in range(T+A[i][0]):
        score = max(DP[i+1][j],score)

print(score)

Solution (Python):



N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()


dp = [[0 for _ in range(T)] for _ in range(N+1)]

for i in range(N):
    for j in range(T):
        
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1])



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

print(ans)

Solution (Python):
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()))

Solution (Python):
import numpy as np
n,t = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
dp = np.array([0]*t)
ans = 0
for a,b in l:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[a:],dp[:-a]+b)
    
    
print(max(ans,dp[-1]))

Solution (Python):
n, t = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(n)]

ab.sort()

dp = [[0] * t for i in range(n+1)]
ans = 0
for i in range(n):
    for j in range(t):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j - ab[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j - ab[i][0]] + ab[i][1])
    now = dp[i][t-1] + ab[i][1]
    ans = max(ans, now)

print(ans)

Solution (Python):
from heapq import heappop, heappush
N,T = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
AB = sorted(AB)

j = 0
ans=0
dp = [[0]*(T+1) for _ in range(N+1)]
for i in range(N):
  for t in range(T+1):
    dp[i+1][t]=max(dp[i+1][t],dp[i][t])
    if t<=T-1:
      dp[i+1][min(T,t+AB[i][0])]=max(dp[i+1][min(T,t+AB[i][0])],dp[i][t]+AB[i][1])
print(dp[N][T])

Solution (Python):
N,T = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
A.insert(0,[-1,-1])
dp = [[0 for _ in range(T+1)] for _ in range(N)]
for i in range(1,N):
    for j in range(1,T+1):
        dp[i][j] = dp[i-1][j]
        if j>A[i][0]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-A[i][0]]+A[i][1])
dmax = 0
for i in range(1,N+1):
    dmax = max(dmax,dp[i-1][T]+A[i][1])
print(dmax)

Solution (Python):
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
dp=[[0]*(t+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(t+1):
    if j!=t:
      if j-l[i-1][0]>=0:
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+l[i-1][1])
    dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[n]))

Solution (Python):
import numpy as np
N,T = map(int,input().split())
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))
AB.sort(key=lambda x:(x[0],-x[-1]))
dp = np.array([0]*T)
ans = 0
for a,b in AB:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[:-a]+b,dp[a:])
print(max(ans,dp[-1]))

Solution (Python):
N,T = map(int,input().split())
food = [list(map(int,input().split())) for i in range(N)]

dp1 = [[0 for t in range(T+1)] for i in range(N+1)]

for i in range(1,N+1):
    time,deliciousness = food[i-1]
    for t in range(1,T+1):
        if time <= t:
            dp1[i][t] = max(dp1[i-1][t],dp1[i-1][t-time]+deliciousness)
        else:
            dp1[i][t] = dp1[i-1][t]
            
dp2 = [[0 for t in range(T+1)] for i in range(N+1)]

for i in range(N):
    time,deliciousness = food[N-i-1]
    for t in range(1,T+1):
        if time <= t:
            dp2[N-i-1][t] = max(dp2[N-i][t],dp2[N-i][t-time]+deliciousness)
        else:
            dp2[N-i-1][t] = dp2[N-i][t]

ans = 0

for t in range(T):
    for i in range(1,N+1):
        ans = max(ans,dp1[i-1][t]+dp2[i][T-1-t]+food[i-1][1])
        
print(ans)

Solution (Python):
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])


W = T + 1
def dp(AB,W):
    N = len(AB)
    DP = [[0]*W for i in range(N+1)]
    for i in range(N):
        for w in range(W):
            if w != W-1:
                if AB[i][0] <= w:
                    DP[i+1][w] = max(DP[i][w-AB[i][0]]+AB[i][1],DP[i][w])
                else:
                    DP[i+1][w] = DP[i][w]
            else:
                DP[i+1][w] = max(DP[i][w-1]+AB[i][1],DP[i][w])
    return DP

DP1 = dp(AB,W)

ans = DP1[N][T]
print(ans)

Solution (Python):
N,T = map(int,input().split())
tlist=[0]*N
vlist=[0]*N
tvlist=[[0,0]]*N
dp=[[0]*T for i in range(N+1)]

for i in range(N):
    tvlist[i] = list(map(int,input().split()))
tvlist.sort(key=lambda x: x[0])
for i in range(N):
    tlist[i] = tvlist[i][0]
    vlist[i] = tvlist[i][1]

for i in range(N):
    for t in range(T):
        if t>=tlist[i]:
            dp[i+1][t] = max(dp[i][t],dp[i][t-tlist[i]]+vlist[i])
        else:
            dp[i+1][t] = dp[i][t]

ans=0
for i in range(N):
    ans = max(ans,dp[i][T-1]+vlist[i])

print(ans)

Solution (Python):
from numpy import zeros, maximum
N, T, *AB = map(int, open(0).read().split()) 
dp = zeros(6010, int)
for w, v in sorted(zip(*[iter(AB)] * 2)):
  dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)
print(dp.max())

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    l=[]
    for i in range(N):
        A,B=map(int,input().split())
        l.append((A,B))
    l.sort()
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=l[i][0]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-l[i][0]]+l[i][1])
    ans=0
    B_sorted=[x[1] for x in l]
    for i in range(1,N):
        ans=max(ans,dp[i][T-1]+max(B_sorted[i:]))
    print(ans)
        

if __name__ == '__main__':
    main()

Solution (Python):
N,T=map(int,input().split())
G=[list(map(int,input().split())) for _ in range(N)]

G.sort()
dp=[0]*(60000)
for g in G:
    for i in range(T-1,-1,-1):
        dp[i+g[0]]=max(dp[i+g[0]],dp[i]+g[1])
print(max(dp))

Solution (Python):

import sys
INF = float("inf")


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):

    
    
    DP1 = [[0 for _ in range(T+1)] for __ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP1[i][j] = max(DP1[i][j], DP1[i-1][j-A[i-1]]+B[i-1])
            DP1[i][j] = max(DP1[i][j], DP1[i-1][j], DP1[i][j-1])

    
    
    DP2 = [[0 for _ in range(T+1)] for __ in range(N+2)]
    for i in range(N, 0, -1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP2[i][j] = max(DP2[i][j], DP2[i+1][j-A[i-1]]+B[i-1])
            DP2[i][j] = max(DP2[i][j], DP2[i+1][j], DP2[i][j-1])

    
    ans = 0
    for i in range(1, N+1):
        bns = 0
        for j in range(T):
            bns = max(bns, DP1[i-1][j] + DP2[i+1][T-j-1])
        ans = max(ans, bns+B[i-1])
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    T = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)


if __name__ == '__main__':
    main()

Solution (Python):
n,t = map(int,input().split())
dpa = [[0 for i in range(t)] for j in range(n+1)]
dpb = [[0 for i in range(t)] for j in range(n+1)]

for i in range(t):
   dpa[0][i] = 0
   dpb[0][i] = 0
abl = []
for _ in range(n):
   a,b = map(int,input().split())
   abl.append((a,b))

for i in range(n-1):
   for j in range(t):
      if j - abl[i][0] >= 0:
         dpa[i+1][j] = max(dpa[i][j], dpa[i][j-abl[i][0]] + abl[i][1])
      else:
         dpa[i + 1][j] = max(dpa[i][j], dpa[i + 1][j])

abl = abl[::-1]
for i in range(n-1):
   for j in range(t):
      if j - abl[i][0] >= 0:
         dpb[i+1][j] = max(dpb[i][j], dpb[i][j-abl[i][0]] + abl[i][1])
      else:
         dpb[i + 1][j] = max(dpb[i][j], dpb[i + 1][j])

abl = abl[::-1]
ans = 0
for i in range(t):
   for j in range(n):
      ans = max(ans, dpa[j][i]+dpb[n-j-1][t-i-1]+abl[j][1])

print(ans)

Solution (Python):

N,T = map(int,input().split())
AB = [[0,0] for _ in range(N)]

for i in range(N):
    AB[i][0],AB[i][1] = map(int,input().split())

AB.sort()






dp1 =[[0]*T for _ in range(N+1)]

for i in range(N):
    for t in range(1,T):
        dp1[i+1][t] = dp1[i][t]
        if t-AB[i][0]>=0:
            dp1[i+1][t]=max(dp1[i][t],dp1[i][t-AB[i][0]]+AB[i][1])
            
ans=0
for i in range(N):
    ans=max(ans,dp1[i][-1]+AB[i][1])
print(ans)

Solution (Python):
N,T = map(int,input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i],B[i] = map(int,input().split())





dp1 =[[0]*T for _ in range(N+1)]
dp2 =[[0]*T for _ in range(N+1)]

for i in range(N):
    for t in range(1,T):
        dp1[i+1][t] = dp1[i][t]
        if t-A[i]>=0:
            dp1[i+1][t]=max(dp1[i][t],dp1[i][t-A[i]]+B[i])


for i in reversed(range(0,N)):
    for t in range(1,T):
        dp2[i][t] = dp2[i+1][t]
        if t-A[i]>=0:
            dp2[i][t]=max(dp2[i+1][t],dp2[i+1][t-A[i]]+B[i])


ans=0

for i in range(1,N):
    for j in range(0,T):
        ans = max(ans,dp1[i][j]+dp2[i+1][T-1-j]+B[i])
print(ans)

Solution (Python):
def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

N, T = ints()
dp = [[0]*T for j in range(N+1)]
F = sorted([ints() for i in range(N)])

for i in range(N):
  a, b = F[i]

  for t in range(T):
    dp[i+1][t] = max(dp[i+1][t], dp[i][t])
    nt = t+a
    if nt<T:
      dp[i+1][nt] = max(dp[i+1][nt], dp[i][t]+b)

w = max([F[i][1] + dp[i][T-1] for i in range(1, N)])
print(w)

Solution (Python):
n, t = map(int, input().split())
food = []
for i in range(n):
    food.append(list(map(int, input().split())))

food.sort()


dp = [[0 for i in range(t+1)] for j in range(n+1)]

for i in range(n):
    for j in range(t+1):
        a, b = food[i]
        if j == t:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])

        elif j + a >= t:
            dp[i+1][t] = max(dp[i][j] + b, dp[i+1][t])
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])

        else:
            dp[i+1][j+a] = max(dp[i][j] + b, dp[i+1][j+a])
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print(dp[n][t])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort()
dp = [0] * T


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

Solution (Python):
import sys
input = sys.stdin.readline
n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()

dp = [[0 for j in range(t+1)] for i in range(n+1)]

for i in range(n):
    for j in range(t+1):
        dp[i+1][j] =  dp[i][j]
    for j in range(t):
        next = min(j + ab[i][0], t)
        dp[i+1] [next] = max(dp[i+1][next], dp[i][j] + ab[i][1])
print(max(dp[n]))

Solution (Python):
n, t = map(int, input().split())
food = []
for i in range(n):
    food.append(list(map(int, input().split())))
food.sort(key = lambda x:x[0])
b_max = [0 for i in range(n+2)]
for i in range(n):
    b_max[-(i+2)] = max(b_max[-(i+1)], food[-(i+1)][1])
dp = [[0 for i in range(t+1)] for j in range(n+1)]
for i in range(n):
    for j in range(t+1):
        if j + food[i][0] < t:
            dp[i+1][j + food[i][0]] = max(dp[i+1][j + food[i][0]], dp[i][j] + food[i][1])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
ans = 0
for i in range(n+1):
    ans = max(ans, dp[i][-2] + b_max[i+1])
print(ans)

Solution (Python):
import numpy as np
n,t=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
b=np.zeros((n+1,t))
c=np.zeros((n+1,t))
for i in range(n):
    b[i+1]=b[i]
    b[i+1][a[i][0]:]=np.maximum(b[i+1][a[i][0]:],b[i][:-a[i][0]]+a[i][1])
    c[-i-2]=c[-i-1]
    c[-i-2][a[-i-1][0]:]=np.maximum(c[-i-2][a[-i-1][0]:],c[-i-1][:-a[-i-1][0]]+a[-i-1][1])
q=0
for i in range(n):
    q=max(q,max(b[i]+c[i+1][::-1])+a[i][1])
print(int(q))

Solution (Python):
n,t = map(int, input().split())
ls = [list(map(int, input().split())) for i in range(n)]
t-=1
dp1 = [[0 for _ in range(t+1)] for _ in range(n+1)]
for i in range(n+1):
    for j in range(t+1):
        if i>0 and j>=ls[i-1][0]:
                dp1[i][j] = max(dp1[i-1][j-ls[i-1][0]] + ls[i-1][1] ,dp1[i-1][j])

        elif i>0:
            dp1[i][j] = dp1[i-1][j]

dp2 = [[0 for _ in range(t+1)] for _ in range(n+1)]
for i in range(n, -1, -1):
    for j in range(t+1):
        if i<n and j>=ls[i][0]:
                dp2[i][j] = max(dp2[i+1][j-ls[i][0]] + ls[i][1] ,dp2[i+1][j])

        elif i<n:
            dp2[i][j] = dp2[i+1][j]

ans=0
for i in range(n):
    for j in range(t):
        ans = max(dp1[i][j] + dp2[i+1][t-j] + ls[i][1],ans)


print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,T=map(int,input().split())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    dp=[0]*T
    ans=0
    for a,b in AB:
        ndp=dp[:]
        for t in range(T):
            if(t+a<T):
                ndp[t+a]=max(ndp[t+a],dp[t]+b)
            else:
                ans=max(ans,dp[t]+b)
        dp=ndp
    print(ans)
resolve()

Solution (Python):
N,M=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
AB.sort(key=lambda x: x[0])

max_=0
for i in AB:
    if max_<i[0]:
        max_=i[0]

dp=[0]*(max_+M)
max_=0
for i in AB:
    for j in range(M)[::-1]:
        dp[j+i[0]] = max(dp[j+i[0]],dp[j]+i[1])
        
print(max(dp))

Solution (Python):
n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)

Solution (Python):
import numpy as np
def solve(n, t, a, b):
    dp = np.zeros(t, dtype=int)
    candidates = []
    for w, v in sorted(zip(a, b)):
        candidates.append(dp[-1] + v)
        if w > t:
            continue
        dp[w:] = np.maximum(dp[:-w] + v, dp[w:])
    return np.max(candidates)

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, t = LI()
ab = sorted(LIR(n))
dp = [0] * t
ans = 0
for a, b in ab:
    ans = max(ans, dp[-1] + b)
    for i in range(a, t)[::-1]:
        dp[i] = max(dp[i], dp[i - a] + b)


print(ans)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = [list(map(int, readline().split())) for _ in range(n)]
    ab.sort()
    dp = [0] * t
    mv = 0
    for a, b in ab:
        mv = max(mv, dp[-1] + b)
        for i in range(t - 1 - a, -1, -1):
            dp[i+a] = max(dp[i+a], dp[i] + b)
    print(mv)


if __name__ == '__main__':
    solve()

Solution (Python):
N,T=map(int,input().split())
import numpy as np
dp=np.zeros(T,dtype=int)
maxval=0

meals=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  meals[i]=a,b

meals=sorted(meals,key=lambda x:x[0])

for i in range(N):
  a,b=meals[i]
  if maxval<dp[-1]+b:
    maxval=dp[-1]+b
  np.maximum(dp[:-a]+b,dp[a:],out=dp[a:])
  
print(maxval)

Solution (Python):
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
food_l = []
for _ in range(n):
    a, b = map(int, input().split())
    food_l.append((a, b))
food_r = food_l[::-1]

dp_l = [ [0]*t for _ in range(n+1) ]
dp_r = [ [0]*t for _ in range(n+1) ]
for i in range(1, n+1):
    a_l, b_l = food_l[i-1]
    a_r, b_r = food_r[i-1]
    for j in range(t):
        dp_l[i][j] = max(dp_l[i][j], dp_l[i-1][j])
        if j + a_l < t:
            dp_l[i][j+a_l] = max(dp_l[i][j+a_l], dp_l[i-1][j]+b_l)
        
        dp_r[i][j] = max(dp_r[i][j], dp_r[i-1][j])
        if j + a_r < t:
            dp_r[i][j+a_r] = max(dp_r[i][j+a_r], dp_r[i-1][j]+b_r)

ans = 0
for i in range(n):
    res = max(food_l[i][1]+dp_l[i][j]+dp_r[n-i-1][t-j-1] for j in range(t))
    ans = max(res, ans)
print(ans)

Solution (Python):
import numpy as np

N, T = map(int, input().split())
AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

AB.sort()

dp = np.zeros(T, dtype=int)

ans = 0
for a, b in AB:
  ans = max(ans, dp[-1] + b)
  dp[a:] = np.maximum(dp[a:], dp[:-a] + b)

print(ans)

Solution (Python):
N, T = map(int, input().split())
AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

AB.sort()

dp = [[0 for t in range(T)] for i in range(N+1)]

ans = 0
for i, ab in enumerate(AB):
  ans = max(ans, dp[i][T-1] + ab[1])
  for t in range(T):
    if t < ab[0]:
      dp[i+1][t] = dp[i][t]
    else:
      dp[i+1][t] = max(dp[i][t-ab[0]] + ab[1], dp[i][t])

print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n, p = map(int, input().split())
snacks = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
dp = [0 for _ in range(p)]
ans = snacks[0][1]

for i in range(1, n):
	x, y = snacks[i-1]
	z = snacks[i][1]
	for j in range(p-1, 0, -1):
		if j >= x:
			dp[j] = max(dp[j], dp[j-x]+y)
		ans = max(ans, dp[j]+z)

print(ans)

Solution (Python):
n, t = map(int, input().split())
l = []
 
for i in range(n):
  a, b = map(int, input().split())
  l.append((a, b))
 
l.sort()
 
ans = 0
dp = [[0]*t for _ in range(n+1)]
for i in range(n):
  cur = dp[i][t-1] + l[i][1]
  ans = max(ans, cur)
  for j in range(t):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    nj = j+l[i][0]
    if nj < t:
      dp[i+1][nj] = max(dp[i+1][nj], dp[i][j]+l[i][1])
print(ans)

Solution (Python):
n, T = map(int, input().split())
food = []
for _ in range(n):
    a, b = map(int, input().split())
    food.append((a, b))

dp1 = [[0]*T for _ in range(1+n)]
dp2 = [[0]*T for _ in range(1+n)]

for i in range(n):
    for j in range(T):
        dp1[i+1][j] = dp1[i][j]
        if j - food[i][0] >= 0:
            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j-food[i][0]] + food[i][1])

for i in range(n-1, -1, -1):
    for j in range(T):
        dp2[i][j] = dp2[i+1][j]
        if j - food[i][0] >= 0:
            dp2[i][j] = max(dp2[i][j], dp2[i+1][j-food[i][0]] + food[i][1])

res = 0
for i in range(n):
    for j in range(T):
        res = max(res, food[i][1] + dp1[i][j] + dp2[i+1][T-1-j])
print(res)

Solution (Python):
def solve():
    import numpy as np
    from sys import stdin
    f_i = stdin
    
    N, T = map(int, f_i.readline().split())
    AB = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    AB.sort()
    max_Ai = AB[-1][0]
    
    dp = [[0] * T for i in range(N + 1)]
    dp = np.zeros(max_Ai + T, dtype=int)
    
    
    for A_i, B_i in AB:
        dp[A_i:A_i+T] = np.maximum(dp[A_i:A_i+T], dp[:T] + B_i)
    
    print(max(dp))

solve()

Solution (Python):
n, t = map(int, input().split())
l = [[0, 0] for _ in range(n)]
 
for i in range(n):
  a, b = map(int, input().split())
  l[i][0] = a
  l[i][1] = b

l.sort()


ans = 0
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    nj = j+l[i][0]
    if nj < t:
      dp[i+1][nj] = max(dp[i+1][nj], dp[i][j]+l[i][1])
  now = dp[i][t-1] + l[i][1]
  ans = max(ans, now)

print(ans)

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    N, T = map(int, f_i.readline().split())
    AB = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    AB.sort()
    
    dp = [[0] * T for i in range(N + 1)]
    
    for i, AB_i in enumerate(AB, start=1):
        A_i, B_i = AB_i
        dp_i = dp[i]
        dp_pre = dp[i-1]
        dp_i[:A_i] = dp_pre[:A_i]
        for j, t in enumerate(zip(dp_pre[A_i:], dp_pre), start=A_i):
            x, y = t
            if x < y + B_i:
                dp_i[j] = y + B_i
            else:
                dp_i[j] = x
    
    ans = max(dp[k][-1] + AB[k][1] for k in range(N))
    print(ans)

solve()

Solution (Python):
def p_e():
    n, t = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ab.sort()
    ma = ab[-1][0]
    dp = [0] * (t + ma)
    for w, v in ab:
        next = [0] * (t + ma)
        for j in range(1, t + ma):
            if 0 <= j - w < t:
                next[j] = max(dp[j - w] + v, dp[j])
            else:
                next[j] = dp[j]
        dp = next
    print(max(dp))
    
p_e()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,t=map(int,input().split())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    ans=0
    dp=[0]*t
    for a,b in AB:
        ans=max(ans,dp[-1]+b)
        ndp=dp[:]
        for i in range(t):
            if(i+a<t):
                ndp[i+a]=max(ndp[i+a],dp[i]+b)
        dp=ndp

    print(ans)
resolve()

Solution (Python):
N, T = map(int, input().split())
p = []
for i in range(N):
    A, B = map(int, input().split())
    p.append([A, B])
p.sort()

dp = [[0]*3005 for _ in range(3005)]
ans = 0
for i in range(N):
    for j in range(T):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        nextj = j + p[i][0]
        if nextj < T:
            dp[i+1][nextj] = max(dp[i+1][nextj], dp[i][j] + p[i][1])
    now = dp[i][T-1] + p[i][1]
    ans = max(ans, now)

print(ans)

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline

n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

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

dp = np.array([0]*t)
ans = 0

for a, b in ab:
    ans = max(ans, dp[-1] + b)
    dp[a:] = np.maximum(dp[:-a]+b, dp[a:])
print(max(ans, dp[-1]))

Solution (Python):
import numpy as np

n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()
dp = np.array([0]*t)
ans = 0
for a,b in ab:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[:-a]+b,dp[a:])

print(max(ans,dp[-1]))

Solution (Python):
n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort(key=lambda x: x[0])

dp = [[0] * (n+1) for i in range(t)]
ans = 0
for time in range(1, t):
    for i in range(n):
        if ab[i][0] <= time:
            if dp[time][i] < (ab[i][1] + dp[time - ab[i][0]][i]):
                dp[time][i+1] = (ab[i][1] + dp[ time - ab[i][0] ][i])
            else:
                dp[time][i+1] = dp[time][i]
        else:
            dp[time][i+1] = dp[time][i]
        if i < n-1:
            ans = max(ans, dp[time][i+1] + ab[i+1][1])

print(ans)

Solution (Python):
n,t = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([a,b])
dp = [0] * (t)
ab.sort()
m = 0
for i,j in ab:
  pdp,dp = dp,[0] * (t)
  for k in range(t):
    dp[k] = pdp[k]
  for k in range(t):
    if k+i >= t:
      m = max(m,pdp[k]+j)
    else:
      dp[k+i] = max(dp[k+i],pdp[k]+j)
if m == 0:
  print(max(dp))
else:
  print(m)

Solution (Python):
from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)