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



Sample input:
2 60
10 10
100 100


Sample output:
110

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,T = IL()
data = ILL(N)


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


MAX = 0
for i in range(1,N+1):
  tt,vv = data[i-1]
  for t in range(1,T):
    if t >= tt:
      dp[i][t] = max(dp[i-1][t], dp[i-1][t-tt]+vv)
      MAX = max(MAX,dp[i][t])
    else:
      dp[i][t] = dp[i-1][t]
  dp[i][T] = dp[i-1][T-1]+vv
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, t = ns()
    d = [na() for _ in range(n)]
    d.sort(key=lambda x: x[1])

    dp = [-1 for _ in range(t + 3000 + 1)]
    dp[0] = 0

    for a, b in d:
        for i in range(t - 1, -1, -1):
            if dp[i] >= 0:
                dp[i + a] = max(dp[i + a], dp[i] + b)

    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    N, T = list(map(int, input().split()))
    AB = [[]]+[list(map(int, input().split())) for _ in range(N)]
    dp = [[None for _ in range(T+3000)] for __ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(T, -1, -1):
            if dp[i][j] is None:
                continue
            time, value = AB[i+1]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]) if dp[i+1][j] is not None else dp[i][j]
            if j != T:
                dp[i+1][j+time] = max(dp[i+1][j+time], dp[i][j]+value)  if dp[i+1][j+time] is not None else dp[i][j]+value
    #print(dp)
    ans = 0
    for v in dp[N]:
        if v is not None:
            ans = max(ans, v)
    print(ans)
    
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N, T = list(map(int, input().split()))
    AB = [[]]+[list(map(int, input().split())) for _ in range(N)]
    dp = [[None for _ in range(T+3000)] for __ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(T):
            if dp[i][j] is None:
                continue
            time, value = AB[i+1]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]) if dp[i+1][j] is not None else dp[i][j]
            dp[i+1][j+time] = max(dp[i+1][j+time], dp[i][j]+value)  if dp[i+1][j+time] is not None else dp[i][j]+value
    #print(dp)
    ans = 0
    for v in dp[N]:
        if v is not None:
            ans = max(ans, v)
    print(ans)
    
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,t = list(map(int, input().split()))
ab = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
ab.sort(key=lambda x: x[1])
ma,mb = ab[-1]
ab = ab[:-1]
dp = [0]*(t)
prv = [[0]*(t+1) for _ in range(n)]
for i in range(1, n):
    a,b = ab[i-1]
    for j in range(t-1, 0, -1):
#     for j in range(1, t+1):
#         dp[i][j] = dp[i-1][j]
        if j>=a and dp[j]<dp[j-a]+b:
            dp[j] = dp[j-a]+b
            prv[i][j] = j-a
        else:
            prv[i][j] = j
ans = dp[t-1] + mb
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,t = list(map(int, input().split()))
ab = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
    
dp = [0]*(t+1)
prv = [[0]*(t+1) for _ in range(n+1)]
for i in range(1, n+1):
    a,b = ab[i-1]
    for j in range(t, 0, -1):
#     for j in range(1, t+1):
#         dp[i][j] = dp[i-1][j]
        if j>=a and dp[j]<dp[j-a]+b:
            dp[j] = dp[j-a]+b
            prv[i][j] = j-a
        else:
            prv[i][j] = j
ans = 0
for j in range(0, t):
    used = [False]*(n+1)
    jj = j
    for i in range(n, 0, -1):
        nj = prv[i][jj]
        if jj!=nj:
            used[i] = True
        jj = nj
    m = 0
    for i in range(1,n+1):
        if not used[i]:
            m = max(m, ab[i-1][1])
    ans = max(ans, dp[j] + m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,t = list(map(int, input().split()))
ab = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
    
dp = [0]*(t+1)
prv = [[0]*(t+1) for _ in range(n+1)]
for i in range(1, n+1):
    a,b = ab[i-1]
    for j in range(t, 0, -1):
#     for j in range(1, t+1):
#         dp[i][j] = dp[i-1][j]
        if j>=a and dp[j]<dp[j-a]+b:
            dp[j] = dp[j-a]+b
            prv[i][j] = (i-1, j-a)
        else:
            prv[i][j] = (i-1, j)
ans = 0
for j in range(0, t):
    used = [False]*(n+1)
    ii,jj = n,j
    while ii>0 and jj>0:
        ni, nj = prv[ii][jj]
        if jj!=nj:
            used[ii] = True
        ii,jj = ni,nj
    m = 0
    for i in range(1,n+1):
        if not used[i]:
            m = max(m, ab[i-1][1])
    ans = max(ans, dp[j] + m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,t = list(map(int, input().split()))
ab = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
    
dp = [0]*(t+1)
prv = [[0]*(t+1) for _ in range(n+1)]
for i in range(1, n+1):
    a,b = ab[i-1]
    for j in range(t, 0, -1):
#     for j in range(1, t+1):
#         dp[i][j] = dp[i-1][j]
        if j>=a and dp[j]<dp[j-a]+b:
            dp[j] = dp[j-a]+b
            prv[i][j] = (i-1, j-a)
        else:
            prv[i][j] = (i-1, j)
ans = 0
for j in range(1, t):
    used = [False]*(n+1)
    ii,jj = n,j
    while ii>0 and jj>0:
        ni, nj = prv[ii][jj]
        if jj!=nj:
            used[ii] = True
        ii,jj = ni,nj
    m = 0
    for i in range(1,n+1):
        if not used[i]:
            m = max(m, ab[i-1][1])
    ans = max(ans, dp[j] + m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,t = list(map(int, input().split()))
ab = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
    
dp = [0]*(t+1)
prv = [[0]*(t+1) for _ in range(n+1)]
for i in range(1, n+1):
    a,b = ab[i-1]
    for j in range(t, 0, -1):
#     for j in range(1, t+1):
#         dp[i][j] = dp[i-1][j]
        if j>=a and dp[j]<dp[j-a]+b:
            dp[j] = dp[j-a]+b
            prv[i][j] = (i-1, j-a)
        else:
            prv[i][j] = (i-1, j)
ans = 0
for j in range(1, t):
    ind = set()
    ii,jj = n,j
    while ii>0 and jj>0:
        ni, nj = prv[ii][jj]
        if jj!=nj:
            ind.add(ii)
        ii,jj = ni,nj
    m = 0
    for i in range(1,n+1):
        if i not in ind:
            m = max(m, ab[i-1][1])
    ans = max(ans, dp[j] + m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,t = list(map(int, input().split()))
ab = [None]*n
for i in range(n):
    ab[i] = tuple(map(int, input().split()))
    
dp = [[0]*(t+1) for _ in range(n+1)]
prv = [[0]*(t+1) for _ in range(n+1)]
for i in range(1, n+1):
    a,b = ab[i-1]
    for j in range(1, t+1):
        dp[i][j] = dp[i-1][j]
        if j>=a and dp[i][j]<dp[i-1][j-a]+b:
            dp[i][j] = dp[i-1][j-a]+b
            prv[i][j] = (i-1, j-a)
        else:
            prv[i][j] = (i-1, j)
ans = 0
for j in range(1, t):
    ind = set()
    ii,jj = n,j
    while ii>0 and jj>0:
        ni, nj = prv[ii][jj]
        if jj!=nj:
            ind.add(ii)
        ii,jj = ni,nj
    m = 0
    for i in range(1,n+1):
        if i not in ind:
            m = max(m, ab[i-1][1])
    ans = max(ans, dp[n][j] + m)
print(ans)

Submission status: Wrong Answer

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

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

print(dp[-1][-1][0])

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,T = LMIIS()
    AB = []
    for i in range(N):
        AB.append(LMIIS())
    

    dp = [-1] * (T+3001)
    dp[0] = 0
    for a,b in AB:
        tmpdp = dp[:]
        for j in range(T):
            if dp[j] != -1:
                tmpdp[j+a] = max(dp[j+a],dp[j]+b)
        dp = tmpdp
    print(max(dp))






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, A = getNM()
w = []
v = []
for i in range(N):
    a, b = getNM()
    w.append(a)
    v.append(b)

# limit回までコストカットできる
def knapsack_6(N, upper, limit, weight, value):
    dp = [[[0] * (upper + 1) for i in range(limit + 1)] for j in range(N + 1)]

    for i in range(N):
        # ボーナスでコスト１にするのを使ったか 使うと-1する
        for j in range(limit + 1):
            for l in range(upper + 1):
                # デフォルト　elseで下に置けない（場合分けが難しいので）
                dp[i + 1][j][l] = dp[i][j][l]
                # 追加
                if l >= weight[i]:
                    dp[i + 1][j][l] = max(dp[i][j][l], dp[i][j][l - weight[i]] + value[i])
                # 追加（コストカット）
                if l >= 1 and limit >= 1:
                    dp[i + 1][j - 1][l] = max(dp[i][j - 1][l], dp[i][j][l - 1] + value[i])
    return dp[N][0][upper]

print(knapsack_6(N, A, 1, w, v))

Submission status: Wrong Answer

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

ab = sorted(ab, key=lambda x:(x[1], x[0]), reverse=True)

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

Submission status: Wrong Answer

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

ab = sorted(ab, key=lambda x:(x[1], x[0]), reverse=True)

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

import sys
input = sys.stdin.readline


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

    dp = [0] * ((T + 1) * 2)
    ldp = len(dp)

    ans = 0

    AB.sort(key=itemgetter(1), reverse=True)
    AB.sort(key=itemgetter(0))
    for i in range(N):
        a, b = AB[i]
        for j in range(ldp - 1, -1, -1):
            if j - a < 0:
                break
            tmp = dp[j]
            dp[j] = max(dp[j], dp[j - a] + b)
            if tmp < dp[j] and j - a < T:
                ans = max(ans, dp[j])


    print(ans)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


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

    dp = [0] * ((T + 1) * 2)
    ldp = len(dp)

    ans = 0

    AB.sort()
    for i in range(N):
        a, b = AB[i]
        for j in range(ldp - 1, -1, -1):
            if j - a < 0:
                break
            tmp = dp[j]
            dp[j] = max(dp[j], dp[j - a] + b)
            if tmp < dp[j] and j - a < T:
                ans = max(ans, dp[j])


    print(ans)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

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


ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(T+1):
        dp[i+1][t] = max(dp[i+1][t], dp[i][t])

        if t < T:
            # dp[i+1][t+a] = max(dp[i+1][t+a], dp[i][t+a])
            dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])


ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

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


ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

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


ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

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


ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

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

ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(T):
        dp[i+1][t] = max(dp[i+1][t], dp[i][t])
        dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])

ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(T):
        dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])

ans = max(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(N) ]

for i in range(N):
    a,b = abl[i]
    for t in range(T):
        dp[i][t+a] = max(dp[i-1][t]+b, dp[i-1][t+a])

ans = max(dp[N-1])
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())
abl = []
for _ in range(N):
    a,b = map(int, input().split())
    abl.append((a,b))

abl.sort()
dp = [ [0]*6001 for _ in range(3000) ]

for i in range(N):
    a,b = abl[i]
    for t in range(T):
        dp[i][t+a] = max(dp[i-1][t]+b, dp[i-1][t+a])

ans = max(dp[N-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n,t=list(map(int,input().split()))
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x: 10000*x[1]+x[0])

a,b=ab.pop()
ans2=b
t-=1

dp=[[-10**10]*3001 for _ in range(n+1)]
dp[0][0]=0

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

ans2+=bmax

print(ans2)

Submission status: Wrong Answer

Solution code:
n,t=list(map(int,input().split()))
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[1])

ans=0
dp=[[-10**10]*3001 for _ in range(n+1)]
dp[0][0]=0

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

a,b=ab.pop()
ans2=b
t-=1

dp=[[-10**10]*3001 for _ in range(n+1)]
dp[0][0]=0

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

ans2+=bmax

print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
n,t=list(map(int,input().split()))
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[1])

a,b=ab.pop()
ans=b
t-=1

dp=[[-10**10]*3001 for _ in range(n+1)]
dp[0][0]=0

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

ans+=bmax

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N, T = map(int, input().split())
a_list = []
max_a = 0
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append((a, b))
    max_a = max(max_a, a)
a_list.sort(key=itemgetter(0))
dp = [[0 for _ in range(T + max_a)] for _ in range(N + 1)]
for i in range(N):
    for j in range(T + max_a - 1):
        if (j < T):
            dp[i + 1][j + a_list[i][0]] = max(dp[i][j], dp[i][j] + a_list[i][1])
        else:
            dp[i + 1][j + 1] = max(max(dp[i + 1][j], dp[i + 1][j + 1]), dp[i][j + 1])
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
a_list = []
max_a = 0
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append((a, b))
    max_a = max(max_a, a)
a_list.sort(key=lambda x: x[1])
dp = [[0 for _ in range(T)] for _ in range(N)]
for i in range(N - 1):
    for j in range(T - 1):
        if (j + a_list[i][0] < T):
            dp[i + 1][j + a_list[i][0]] = max(dp[i][j], dp[i][j] + a_list[i][1])
        else:
            dp[i + 1][j + 1] = max(max(dp[i + 1][j], dp[i + 1][j + 1]), dp[i][j + 1])
print(max(dp[-1]) + a_list[-1][1])

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
a_list = []
max_a = 0
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append((a, b))
    max_a = max(max_a, a)
a_list.sort(key=lambda x: x[1])
dp = [[0 for _ in range(T + max_a)] for _ in range(N + 1)]
for i in range(N):
    for j in range(T + max_a - 1):
        if (j < T):
            dp[i + 1][j + a_list[i][0]] = max(dp[i][j], dp[i][j] + a_list[i][1])
        else:
            dp[i + 1][j + 1] = max(max(dp[i + 1][j], dp[i + 1][j + 1]), dp[i][j + 1])
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
a_list = []
max_a = 0
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append((a, b))
    max_a = max(max_a, a)
a_list.sort(key=lambda x: x[0])
dp = [[0 for _ in range(T + max_a)] for _ in range(N + 1)]
for i in range(N):
    for j in range(T + max_a - 1):
        if (j < T):
            dp[i + 1][j + a_list[i][0]] = max(dp[i][j], dp[i][j] + a_list[i][1])
        else:
            dp[i + 1][j + 1] = max(max(dp[i + 1][j], dp[i + 1][j + 1]), dp[i][j + 1])
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, t = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))

dp = [[0] * (t+3001) for _ in range(n+1)]
for i in range(1, n+1):
    a, b = ab[i-1]
    for j in range(t):
        dp[i][j+a] = max(dp[i-1][j+a], dp[i-1][j] + b)

ans = 0
for i in range(t-1, t + 3001):
    ans = max(ans, dp[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, t = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))

dp = [[0] * (t+3001) for _ in range(n+1)]
s = 0
for i in range(1, n+1):
    a, b = ab[i-1]
    s += b
    for j in range(t):
        dp[i][j+a] = max(dp[i-1][j+a], dp[i-1][j] + b)

ans = 0
for i in range(t, t + 3001):
    ans = max(ans, dp[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, t = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))

dp = [[0] * (t+1) for _ in range(n+1)]
s = 0
for i in range(1, n+1):
    a, b = ab[i-1]
    s += b
    for j in range(t-1):
        dp[i][min(t, j+a)] = max(dp[i-1][min(t, j+a)], dp[i-1][j] + b)
print(dp[n][t])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, t = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(1))

dp = [[0] * (t+1) for _ in range(n+1)]
s = 0
for i in range(1, n+1):
    a, b = ab[i-1]
    s += b
    for j in range(t-1):
        dp[i][min(t, j+a)] = max(dp[i-1][min(t, j+a)], dp[i-1][j] + b)
print(dp[n][t])