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: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,t = m()

li = [l() for i in range(n)]

ma = []
for i in range(n):
    ma.append([li[i][1],i])

ma.sort(reverse = True)


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

for i in range(n):
    for k in range(li[i][0]+t,li[i][0]-1,-1):
        if dp[k] <= dp[k-li[i][0]] + li[i][1]:
            dp[k] = dp[k-li[i][0]] + li[i][1]


dp.sort(reverse = True)
ans = dp[0]

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab2 = [ab[i] for i in range(N) if ab[i][0] >= T]
ab2.append([0,0])
ab.sort(key=lambda x: x[1])

c = ab[-1][0]
ans = ab[-1][1]
i = 2
while(c<T):
    c+=ab[-i][0]
    ans += ab[-i][1]
    i += 1

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

ab.sort(key=lambda x: x[0])
ab2.sort(key=lambda x: x[1])
for i in reversed(range(1,N)):
    for j in range(T):
        if j < ab[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-ab[i][0]] + ab[i][1])
    tmp = dp[i][T-1] + max(ab[i-1][1],ab2[-1][1])
    ans = max(ans, tmp)
ans = max(ans,ab[0][1] + ab2[-1][1])
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
def knapsack(N,W,weight,value):
    dp = np.zeros(((N+1),(W+1)))
    F=[[[] for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        for w in range(W+1):
            if weight[i]<=w:
                if dp[i][w-weight[i]]+value[i] <= dp[i][w]:
                    dp[i+1][w]=dp[i][w]
                    F[i+1][w] =F[i][w]
                else:
                    dp[i+1][w] = dp[i][w-weight[i]]+value[i]
                    F[i+1][w] = F[i][w-weight[i]] + [i]
            else:
                dp[i+1][w]=dp[i][w]
                F[i+1][w] =F[i][w]
    return dp[N][W],F[N][W]

if __name__ == "__main__":
    N,T = map(int,input().split())
    D = []
    E = []
    for i in range(N):
        A,B = map(int,input().split())
        D.append(A)
        E.append(B)
    ans,F = knapsack(N,T-1,D,E)
    max = 0
    for i in range(N):
        if i in F:
            continue
        if max <= E[i]:
            max = E[i]
    print(int(ans+max))

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
weight = []
value = []

dp = [[0] * (6010) for i in range(3010)]

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
#配る
addi = set([])
for i, (ww, vv) in enumerate(zip(weight, value)):
    for w in range(T):            
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
        if w+W >= T:
            addi.add(w+W)
        dp[i+1][w+ww] = max(dp[i][w+ww], dp[i][w] + vv)
        #else: dp[i+1][w] = dp[i][w]

    for w in addi:
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])


print(max(dp[N]))
"""
for i, v in enumerate(dp[N][:200]):
    print("{}:{}, ".format(i, v), end="")
"""

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())
dish = sorted([list(map(int, input().split()))
               for i in range(n)], reverse=True, key=lambda x: x[1])
ans = 0
cnt = 0
res = []
for d in dish:
    if cnt + d[0] < t:
        ans += d[1]
        cnt += d[0]
    else:
        res.append(d[1])

ans += max(res)
print(ans)

Submission status: Runtime Error

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

def answer():
    N, T = map(int, input().split())
    dishes = [list(map(int, input().split())) for _ in range(N)]
    dishes = sorted(dishes, key=lambda x: x[1], reverse=True)

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

    def search(i, u):
        if dp[i][u]:
            return dp[i][u]
        if i == N:
            result = 0
        elif u > T - 0.5:
            result = search(i+1, u)
        else:
            w = dishes[i][0]
            v = dishes[i][1]

            res1 = search(i+1, u)
            res2 = search(i+1, u-w) + v
            result = max(res1, res2)

        dp[i][u] = result
        return result

    print(search(0, T-1))


if __name__ == '__main__':
    answer()

Submission status: Runtime Error

Solution code:
dishes = input().split()
dish_utility = []
dish_utility_all = []
t = 0
total_utility = 0
j = 0

for i in range(int(dishes[0])):
    dish = input().split()
    dish_utility.append(int(dish[1])/int(dish[0]))
    dish_utility.append(int(dish[0]))
    dish_utility.append(int(dish[1]))
    dish_utility_all.append(dish_utility)
    dish_utility = []
    
dish_utility_all.sort(reverse = True)    
time = int(dishes[1]) - 5
best = dish_utility_all.pop(0)

while t < time:
    total_utility += dish_utility_all[j][2]
    t += dish_utility_all[j][1]
    j += 1

total_utility += best[2]
print(total_utility)

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())

a = [0]*3333
b = [0]*3333
dp = [0]*6666


for i in range(1, n+1):
	a[i], b[i] = map(int, input().split())

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

#print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n,t = _ia()
ab = []
asum = 1
imax = -1
amax = -1
bmax = -1
for i in range(n):
    _a,_b = _ia()
    ab.append((_a,_b))
    asum += _a
    if bmax<0 or (_b>=bmax and _a>ab[imax][0]):
        imax = i
        amax = _a
        bmax = _b
#
dp = [ 0 ] * (asum)
for i, _ab in enumerate(ab):
    if i==imax: continue
    a,b = _ab
    prev = dp.copy()
    for atot in range(asum):
        if atot>=a:
            dp[atot] = max(prev[atot],prev[atot-a]+b)
        else:
            dp[atot] = prev[atot]
#
if t>asum:
    print(dp[-1]+bmax)
else:
    print(max(dp[t-1]+bmax,dp[t]))

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())

a = [0]*3333
b = [0]*3333
dp = [0]*3333


for i in range(1, n+1):
	a[i], b[i] = map(int, input().split())

for i in range(1, n+1):
	for j in range(6000, 0, -1):
		if ((a[i] <= j) and ((j-a[i])<t)):
			dp[j] = max(dp[j], dp[j - a[i]] + b[i])

#print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
weight = []
value = []

dp = [[0] * (3010) for i in range(6010)]

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
#配る
for i, (ww, vv) in enumerate(zip(weight, value)):
    for w in range(T):            
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
        dp[i+1][w+ww] = max(dp[i][w+ww], dp[i][w] + vv)
        #else: dp[i+1][w] = dp[i][w]


print(max(dp[N]))
"""
for i, v in enumerate(dp[N][:200]):
    print("{}:{}, ".format(i, v), end="")
"""

Submission status: Runtime Error

Solution code:
def rec(i,j,sho):
    res=0
    if(i==n):
        res=0
    else:
        tisai=max(sho,w[i])
        if(j+tisai>w[i]):
            res=max(rec(i+1,j,sho) , rec(i+1,j-w[i],tisai)+v[i])
        else:
            res=rec(i+1,j,sho)
        return res

    #elif(j<w[i]):
    #    res=rec(i+1,j)
    #else:
    #    res=max(rec(i+1,j) , rec(i+1,j-w[i])+v[i])
    return res
    
n,t=map(int,input().split())
w=[]
v=[]
for i in range(n):
    temp1,temp2=map(int,input().split())
    w.append(temp1)
    v.append(temp2)
#print(w,v)

print(rec(0,t,0))

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O4")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
//#define MOD (ll)(998244353)
#define MOD (ll)(1e9+7)
#define INF (1e17)
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

int dp[3010][6010];

int32_t main() {
#ifdef LOCAL_TEST
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\input.in","r",stdin);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\output.out","w",stdout);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\error.out","w",stderr);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);

	//code...
	int n,t; cin>>n>>t;
	memset(dp,sizeof(dp),0);
	vector<int> w(n+1),v(n+1);
	For(i,1,n) cin>>w[i]>>v[i];
	int ans=0;
	For(i,1,n) For(j,1,6000){
		dp[i][j]=dp[i-1][j-1];
		if(j<t+w[i] && j>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
		ans=max(ans,dp[i][j]);
	}
	cout<<ans<<"\n";
	return 0;
}

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
weight = []
value = []

dp = [[0] * (3010) for i in range(3010)]

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
#配る
for i, (ww, vv) in enumerate(zip(weight, value)):
    for w in range(T):            
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
        dp[i+1][w+ww] = max(dp[i][w+ww], dp[i][w] + vv)
        #else: dp[i+1][w] = dp[i][w]


print(max(dp[N]))
"""
for i, v in enumerate(dp[N][:200]):
    print("{}:{}, ".format(i, v), end="")
"""

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n,t = _ia()
ab = []
asum = 1
imax = -1
amax = -1
bmax = -1
for i in range(n):
    _a,_b = _ia()
    ab.append((_a,_b))
    asum += _a
    if bmax<0 or (_b>=bmax and _a>ab[i-1][0]):
        imax = i
        amax = _a
        bmax = _b
#
del(ab[imax])
asum -= amax
dp = [ 0 ] * (asum)
for a, b in ab:
    prev = dp.copy()
    for atot in range(asum):
        if atot>=a: dp[atot] = max(prev[atot],prev[atot-a]+b)
        else: dp[atot] = prev[atot]
#
if t>asum: print(dp[-1]+bmax)
else: print(max(dp[t-1]+bmax,dp[t]))

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split(" ")))
b = []
c = []
temp = 0
i = 0
deli = 0
for x in range(a[0]):
    e = list(map(int, input().split(" ")))
    b.append(e[1])
    c.append(e[0])

sd = sorted(b, reverse=True)
st = sorted(c)

while temp < a[1] and i < len(sd):
    temp += c[b.index(sd[i])]
    deli += sd[i]

    //print(c[b.index(sd[i])], sd[i])
    i += 1

print(deli)

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O4")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
//#define MOD (ll)(998244353)
#define MOD (ll)(1e9+7)
#define INF (1e17)
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

int dp[6010][6010];

int32_t main() {
#ifdef LOCAL_TEST
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\input.in","r",stdin);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\output.out","w",stdout);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\error.out","w",stderr);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);

	//code...
	int n,t; cin>>n>>t;
	memset(dp,sizeof(dp),0);
	vector<int> w(n+1),v(n+1);
	For(i,1,n) cin>>w[i]>>v[i];
	int ans=0;
	For(i,1,n) For(j,1,6000){
		dp[i][j]=dp[i-1][j-1];
		if(j<t+w[i] && j>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
		ans=max(ans,dp[i][j]);
	}
	cout<<ans<<"\n";
	return 0;
}

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
weight = []
value = []

dp = [[0] * (3010) for i in range(3010)]

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
#配る
for i, (ww, vv) in enumerate(zip(weight, value)):
    for w in range(T):
        if i == 0:
            print(ww, vv)
            
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
        dp[i+1][w+ww] = max(dp[i][w+ww], dp[i][w] + vv)
        #else: dp[i+1][w] = dp[i][w]


print(max(dp[N]))
"""
for i, v in enumerate(dp[N][:200]):
    print("{}:{}, ".format(i, v), end="")
"""

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
weight = []
value = []

dp = [[0] * (3010) for i in range(6010)]

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

max_A = max(weight)
#配る
for i, (ww, vv) in enumerate(zip(weight, value)):
    for w in range(T):
        if i == 0:
            print(ww, vv)
            
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
        dp[i+1][w+ww] = max(dp[i][w+ww], dp[i][w] + vv)
        #else: dp[i+1][w] = dp[i][w]


print(max(dp[N]))
"""
for i, v in enumerate(dp[N][:200]):
    print("{}:{}, ".format(i, v), end="")
"""

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
ans=0
ab.sort(key=lambda x:x[0])
ab.sort(key=lambda x:x[1], reverse=True)
g=[]
f=[]
for i in range(n):
    a,b=ab[i]
    c=0
    now=0
    ok=[]
    no=[]
    for j in range(n):
        if i==j:
            continue
        now+=ab[j][0]
        if now<t:
            c+=ab[j][1]
            ok.append(ab[j])
        else:
            now-=ab[j][0]
            no.append(ab[j])
    if ans<c+b:
        ans=c+b
        g=ok
        f=no

g.sort(key=lambda x:x[1])
f.sort(key=lambda x:x[1],reverse=True)
ans2=ans
if f:
    ans2+=f[0][1]-g[0][1]

print(max(ans,ans2))

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
ns = [[0] * t for i in range(n + 1)]

for i in range(n):
  a[i], b[i] = map(int, input().split())

ns[1][a[0]] = b[0]
_max = 0

for i in range(1, n):
  for j in range(t):
    ns[i + 1][j] = max(ns[i][j], ns[i + 1][j])
    if ns[i][j] > 0:
      if j + a[i] < t:
        ns[i + 1][j + a[i]] = max(ns[i][j] + b[i], ns[i + 1][j + a[i]])
      else:
        _max = max(_max, ns[i][j] + b[i])

print(max(max(ns[n]), _max))

Submission status: Runtime Error

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

def dfs(i, sum, time, remain):
    global answer
    if i == N or time >= T:
        if time < T and len(remain) >= 1:
            sum += AB[max(remain)][1]
        if sum > answer:
            answer = sum
    else:
        dfs(i+1, sum, time, remain)
        if time < T:
            dfs(i+1, sum + AB[i][1], time + AB[i][0], remain-{i})

answer = 0
dfs(0, 0, 0, set(range(N)))
print(answer)

Submission status: Runtime Error

Solution code:
import math

def getsatisfaction(satisfication, V, T):
    if T <= 0:
        return satisfication
    satisfication_tmp=satisfication
    for idx in range(len(V)):
        tmp=V[idx]
        if (tmp==[0,0]):
            continue
        V[idx]=[0,0]
        s=getsatisfaction(satisfication+tmp[1],V,T-tmp[0])
        if (satisfication_tmp < s):
            satisfication_tmp = s
        V[idx]=tmp
    return satisfication_tmp


N,T=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
print(getsatisfaction(0, List, T))

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split())
food = list(list(map(int,input().split()))for i in range(N))
ans = 0
if T == 1:
    for _,i in food:
        ans = max(i,ans)
    print(ans)
    exit()
DP = [[0]*(T) for i in range(N+1)]
for i in range(N):
    a,b = food[i]
    for j in range(a):
        DP[i+1][j] = DP[i][j]
    for j in range(a,T):
        DP[i+1][j] = max(DP[i][j],DP[i][j-a]+b)
ans = 0
i = N
j = T-1
while i > 0 and j > 0:
    if DP[i][j] == DP[i][j-1]:
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    else:
        food[i-1][1] = 0
        j -= food[i-1][0]
        i -= 1
food.sort(reverse=True,key= lambda x:x[1])
print(DP[-1][-1]+food[0][1])

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())
L = []
for i in range(n):
    a, b = map(int, input().split())
    c = b / a
    L.append((a, b, c))

L.sort(key=lambda x:x[2], reverse=True)
summation = 0
while t-1 >= 0:
    for i, elm in enumerate(L):
        if elm[0] <= t-1:
            L.pop(i)
            summation += elm[1]
            t -= elm[0]
            break
    else:
        break

resmax = max(L, key=lambda x:x[1])[1]
summation += resmax

print(summation)

Submission status: Runtime Error

Solution code:
package main

import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
  "sort"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

type Food struct {
  A int
  B int
}
type Foods []Food
func (F Foods) Len() int { return len(F) }
func (F Foods) Less(i, j int) bool { return F[i].A < F[j].B }
func (F Foods) Swap(i, j int) { F[i], F[j] = F[j], F[i] }

func Max(x, y int) int {
  if x < y { return y }
  return x
}

func Min(x, y int) int {
  if x < y { return x }
  return y
}

func main() {
  NT := NextIntVec()
  N, T := NT[0], NT[1]
  F := make([]Food, N)
  for i := range F {
    AB := NextIntVec()
    F[i] = Food{AB[0], AB[1]}
  }
  sort.Sort(Foods(F))
  DP := make([][]int, N)
  for i := range DP {
    DP[i] = make([]int, T)
  }
  for i := 0; i < N - 1; i++ {
    for j := 1; j < T; j++ {
      DP[i + 1][j] = Max(DP[i][j], DP[i + 1][j - 1])
      if F[i].A <= j {
        DP[i + 1][j] = Max(DP[i][j - F[i].A] + F[i].B, DP[i + 1][j])
      }
    }
  }
  H := 0
  for i, dp := range DP {
    H = Max(dp[T - 1] + F[i].B, H)
  }
  Write(H)
  Output()
}

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
dp=[-1 for i in range(t+1)]
s=[0 for i in range(t+1)]
d=[]
dp[0]=0
s[0]=0
for i in range(n):
    d.append(list(map(int,input().split())))
d=sorted(d,key=lambda x: -x[1])
for i in range(n):
    for j in range(t,-1,-1):
        if dp[j]>=0 and j+d[i][0]<=t:
            if dp[j+d[i][0]]<dp[j]+d[i][1]:
                dp[j+d[i][0]]=dp[j]+d[i][1]
                if i<n:
                    s[j+d[i][0]]=d[i+1][1]
ans=0
for i in range(t):
    ans=max(ans,dp[i]+s[i])
print(max(ans,dp[t]))

Submission status: Runtime Error

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

def dfs(i, sum, time, remain):
    global answer
    if i == N:
        if time < T and len(remain) >= 1:
            sum += AB[max(remain)][1]
        if sum > answer:
            answer = sum
    else:
        dfs(i+1, sum, time, remain)
        if time < T:
            dfs(i+1, sum + AB[i][1], time + AB[i][0], remain-{i})

answer = 0
dfs(0, 0, 0, set(range(N)))
print(answer)

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split())
food = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(T) for i in range(N+1)]
for i in range(N):
    a,b = food[i]
    for j in range(a):
        DP[i+1][j] = DP[i][j]
    for j in range(a,T):
        DP[i+1][j] = max(DP[i][j],DP[i][j-a]+b)
ans = 0
i = N
j = T-1
while i > 0 and j > 0:
    if DP[i][j] == DP[i][j-1]:
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    else:
        food[i-1][1] = 0
        j -= food[i-1][0]
        i -= 1
food.sort(reverse=True,key= lambda x:x[1])
print(DP[-1][-1]+food[0][1])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[[() for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.append(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]

n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
L=[0 for i in range(n)]
m=0
for i in range(len(y)):
  L[y[i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print(x+max(M))

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split())
food = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(T) for i in range(N+1)]
for i in range(N):
    a,b = food[i]
    for j in range(a):
        DP[i+1][j] = DP[i][j]
    for j in range(a,T):
        DP[i+1][j] = max(DP[i][j],DP[i][j-a]+b)
ans = 0
i = N
j = T-1
while i > 0 and j > 0:
    if DP[i][j] == DP[i][j-1]:
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    else:
        food[i-1][1] = 0
        i -= 1
        j -= food[i][0]
food.sort(reverse=True,key= lambda x:x[1])
print(DP[-1][-1]+food[0][1])

Submission status: Runtime Error

Solution code:
import numpy as np
class Item:
    def __init__(self,w=0,p=0):
        self.weight=w
        self.price=p

N, T = map(int, input().split())
l = list()
for n in range(N):
    l.append([int(x) for x in input().split()])
items = list()
for x in l:
    items.append(Item(x[0],x[1]))
def knapsack(i, w):
    if i>=len(items):
        return 0
    elif  w < 0.5:
        return knapsack(i+1, w)
    else:
        p1 = knapsack(i+1, w)
        p2 = knapsack(i+1, w - items[i].weight) + items[i].price
        if p1>p2:
            return p1
        else:
            return p2

p = knapsack(0, T)
print(p)

Submission status: Runtime Error

Solution code:
import numpy as np
class Item:
    def __init__(self,w=0,p=0):
        self.weight=w
        self.price=p

N, T = map(int, input().split())
l = list()
for n in range(N):
    l.append([int(x) for x in input().split()])
l = np.array(sorted(l, key=lambda x:x[0]))
items = list()
for x in l:
    items.append(Item(x[0],x[1]))
def knapsack(i, w):
    if i>=len(items):
        return 0
    elif  w < 0.0:
        return knapsack(i+1, w)
    else:
        p1 = knapsack(i+1, w)
        p2 = knapsack(i+1, w - items[i].weight) + items[i].price
        if p1>p2:
            return p1
        else:
            return p2
if np.sum(l[:,0][:-1]) < T:
    print(np.sum(l[:,1]))
else:
    p = knapsack(0, T)
    print(p)

Submission status: Runtime Error

Solution code:
N,T = list(map(int,input().split()))
class Item:
    def __init__(self,w=0,p=0):
        self.weight=w
        self.price=p
AB = [Item(*map(int,input().split())) for i in range(N)]

AB.sort(key = lambda x:x.price)

# coding: utf-8                                                                                                                        
def knapsack(i, w, items):
    if i>=len(items):
        return 0
    elif  w - items[i].weight < 0.0:
        return knapsack(i+1, w, items)
    else:
        p1 = knapsack(i+1, w,items)
        p2 = knapsack(i+1, w - items[i].weight, items) + items[i].price
        if p1>p2:
            return p1
        else:
            return p2
P=[]
for i in range(N):
    i2 = AB[:i] + AB[i+1:]
    p = knapsack(0, T-1, i2)
    P.append(p+AB[i].price)

print(max(P))

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()
dp=[[-1]*t for i in range(n)]
for i in range(n):
    dp[i][0]=0
a,b=ab[0]
dp[0][a]=b
for i in range(1,n):
    a,b=ab[i]
    for j in range(min(a,t)):
        dp[i][j]=dp[i-1][j]
    for j in range(a,t):
        if dp[i-1][j-a]==-1:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-a]+b)
table=[0]*n
table[n-1]=ab[n-1][1]
for i in range(n-2,-1,-1):
    table[i]=max(table[i+1],ab[i][1])
ans=0
for i in range(n-1):
    c=max(dp[i])
    ans=max(ans,c+table[i+1])
print(ans)

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())

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

dp = [[None] * (3000 + 1) for _ in range(3000 + 1)]
def f(i=0, time=0):
    if time >= t:
        return 0
    if i >= n:
        return 0
    if dp[i][time] is not None:
        return dp[i][time]
    r = max(f(i + 1, time + ab[i][0]) + ab[i][1], f(i + 1, time))
    dp[i][time] = r
    return r

print(f())

Submission status: Runtime Error

Solution code:
import numpy as np

def knapsack2(N,W,weight,value,WW):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(WW)] for j in range(N+1)]
  for i in range(WW):
      dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(WW):
      if weight[i]<=w:
        if w-weight[i]>=W: #時間切れ
          dp[i+1][w]=dp[i][w]
        else: #注文可能
          dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #NG
        dp[i+1][w]=dp[i][w]
  return np.max(np.array(dp))
  #return dp[N][2*W]

N, T = map(int,input().split())
WW = T+3000
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

weight = [elem[0] for elem in ab]
value = [elem[1] for elem in ab]
res = knapsack2(N,T,weight,value,WW)
print(res)

Submission status: Runtime Error

Solution code:
dp = [[-1 for i in range(6005)] for j in range(6005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
data = []
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    data.append([a,b])
    A.append(a)
    B.append(b)

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

print(f(0, 0))

Submission status: Runtime Error

Solution code:
dp = [[-1 for i in range(6005)] for j in range(6005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    A.append(a)
    B.append(b)

print(f(0, 0))

Submission status: Runtime Error

Solution code:
dp = [[-1 for i in range(3005)] for j in range(3005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    A.append(a)
    B.append(b)

print(f(0, 0))

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
ab=[tuple(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda x:x[1],reverse=True)
ab.sort(key=lambda x:x[0])
ans=0
now=0
t-=0.5
x=0
while now<=t:
    ans+=ab[x][1]
    now+=ab[x][0]
    x+=1

ab.sort(key=lambda x:x[1],reverse=True)
ans2=0
now=0
t-=0.5
x=0
while now<=t:
    ans2+=ab[x][1]
    now+=ab[x][0]
    x+=1

print(max(ans,ans2))

Submission status: Runtime Error

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))


#処理内容
def main():
	N, T = getlist()
	K = []
	for i in range(N):
		A, B = getlist()
		K.append([A, B])
	DP = [[0 for i in range(T)] for j in range(N + 1)]
	for i in range(N):
		W, V = K[i][0], K[i][1]
		for j in range(T):
			if j < W:
				DP[i + 1][j] = DP[i][j]
			else:
				DP[i + 1][j] = max(DP[i][j], DP[i][j - W] + V)
	ans = DP[-1][-1]
	use = [0] * N
	Y = T - 1
	for i in range(N):
		if DP[N - i][Y] != DP[N - i - 1][Y]:
			use[N - 1 - i] = 1
			Y -= K[-1 - i][0]
	lis = []
	for i in range(N):
		if use[i] == 0:
			lis.append(K[i][1])
	lis = sorted(lis)
	ans += lis[-1]
	print(ans)



if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 


#x,y = [int(i) for i in readline().split()]
#n = int(input())

n,t = [int(i) for i in readline().split()]
ab = [[int(i) for i in readline().split()] for i in range(n)]


dp = [0]*(t+1)

for a,b in ab:
    c = max(dp[t-a:t])
    dp[-1] = max(dp[-1],c+b)
    
    for i in range(t-1,-1,-1):
        if i-a >= 0:
            dp[i] = max(dp[i], dp[i-a] + b)
        else:
            break
    
    #print(dp)

print(max(dp))