Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
weight=[0]*N;value=[0]*N
sumv=0
for i in range(N):
    weight[i],value[i]=map(int,input().split())
    sumv+=value[i]
dp=[[10**12]*(sumv+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(sumv+1):
        if(value[i]<=j):
            dp[i+1][j]=min(dp[i][j-value[i]]+weight[i],dp[i][j])
        else:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
res=0
for i in range(sumv+1):
    if(dp[N][i]<=W):
        res=max(res,i)
print(res)

Submission status: Runtime Error

Solution code:
N,W = list(map(int, input().split()))
w = []
v = []
for _ in range(N):
    a,b = list(map(int, input().split()))
    w.append(a)
    v.append(b)

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

for i in range(N):
    for j in range(W+1):
        if j - w[i] < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]] + v[i])

k = max(dp)
print(max(k))

Submission status: Runtime Error

Solution code:
N,W = list(map(int, input().split()))
w = []
v = []
for _ in range(N):
    a,b = list(map(int, input().split()))
    w.append(a)
    v.append(b)

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

for i in range(N):
    for j in range(W+1):
        if j - w[i] < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]] + v[i])

print(max(max(dp)))

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

sum_ws_m = sum(ws_m)

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[0]*(3*N+2) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N+1):
            # もらうDP
            # j-wなら、新しくwをナップサックに入れて価値が増えるか見る
            if ws[0]*(n+1)+j+w <= W:
                dp[i+1][n+1][j+w] = max(dp[i+1][n+1][j+w], dp[i][n][j]+v)
            # 追加できない場合は以前の情報を更新
                
            dp[i+1][n][j] = max( dp[i+1][n][j], dp[i][n][j] )
            # if dp[i][n][j] == -1: continue
            # # if j + n*ws[0] > W: continue
            # # print("check",i,n,j,v)    )
            # dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
        # print(dp[i+1][n])
ans= 0
for i,As in enumerate(dp[N]):
    w = min( W - i*ws[0], sum_ws_m )
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

sum_ws_m = sum(ws_m)

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[0]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N+1):
            # もらうDP
            # j-wなら、新しくwをナップサックに入れて価値が増えるか見る
            if ws[0]*(n+1)+j+w <= W:
                dp[i+1][n+1][j+w] = max(dp[i+1][n+1][j+w], dp[i][n][j]+v)
            # 追加できない場合は以前の情報を更新
                
            dp[i+1][n][j] = max( dp[i+1][n][j], dp[i][n][j] )
            # if dp[i][n][j] == -1: continue
            # # if j + n*ws[0] > W: continue
            # # print("check",i,n,j,v)    )
            # dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
        # print(dp[i+1][n])
ans= 0
for i,As in enumerate(dp[N]):
    w = min( W - i*ws[0], sum_ws_m )
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            # もらうDP
            if j-w >= 0:
                dp[i+1][n+1][j] = max(dp[i][n+1][j], dp[i][n][j-w]+v)
            else:
                dp[i+1][n+1][j] = dp[i][j+1][k]
            # if dp[i][n][j] == -1: continue
            # # if j + n*ws[0] > W: continue
            # # print("check",i,n,j,v)    )
            # dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(min(sum(ws_m,W-n*ws[0]))+1):
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(W-n*ws[0]+1):
            if dp[i][n][j] == -1: continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            # else:
                # dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Runtime Error

Solution code:
#13:32
n,u = map(int,input().split())
now = [[0 for _ in range(301)] for _ in range(101)]
for i in range(n):
  w,v = map(int,input().split())
  if i == 0:
    w0 = int(w)
  last = now
  now = [[0 for _ in range(301)] for _ in range(101)]
  for j in range(100):
    for k in range(298):
      now[j][k] = max(now[j][k],last[j][k])
      now[j+1][k+w-w0] = max(now[j+1][k+w-w0],last[j][k]+v)
can = []
for j in range(101):
  utmp = u - w0 * j
  if utmp < 0:
    break
  if utmp > 300:
    umtp = 300
  can.append(now[j][utmp])
print(max(can))

Submission status: Runtime Error

Solution code:
#13:32
n,u = map(int,input().split())
now = [[0 for _ in range(301)] for _ in range(101)]
for i in range(n):
  w,v = map(int,input().split())
  if i == 0:
    w0 = int(w)
  last = now
  now = [[0 for _ in range(301)] for _ in range(101)]
  for j in range(100):
    for k in range(298):
      now[j][k] = max(now[j][k],last[j][k])
      now[j+1][k+w-w0] = max(now[j+1][k+w-w0],last[j][k]+v)
can = []
for j in range(101):
  utmp = u - w0 * j
  if utmp < 0:
    break
  if utmp > 300:
    umtp = 301
  can.append(now[j][utmp])
print(max(can))

Submission status: Runtime Error

Solution code:
#13:32
n,u = map(int,input().split())
now = [[0 for _ in range(301)] for _ in range(101)]
for i in range(n):
  w,v = map(int,input().split())
  if i == 0:
    w0 = int(w)
  last = now
  now = [[0 for _ in range(301)] for _ in range(101)]
  for j in range(100):
    for k in range(298):
      now[j][k] = max(now[j][k],last[j][k])
      now[j+1][k+w-w0] = max(now[j+1][k+w-w0],last[j][k]+v)
can = [0]
for j in range(101):
  utmp = u - w0 * j
  if utmp < 0:
    break
  can.append(now[j][utmp])
print(max(can))

Submission status: Runtime Error

Solution code:
#13:32
n,u = map(int,input().split())
now = [[0 for _ in range(301)] for _ in range(101)]
for i in range(n):
  w,v = map(int,input().split())
  if i == 0:
    w0 = int(w)
  last = now
  now = [[0 for _ in range(301)] for _ in range(101)]
  for j in range(100):
    for k in range(298):
      now[j][k] = max(now[j][k],last[j][k])
      now[j+1][k+w-w0] = max(now[j+1][k+w-w0],last[j][k]+v)
can = []
for j in range(101):
  utmp = u - w0 * j
  if utmp < 0:
    break
  can.append(now[j][utmp])
print(max(can))

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
w,v=[0]*N,[0]*N
for i in range(N):
	w[i],v[i]=map(int,input().split())

V=sum(v)
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
dp=[[float("inf")]*(V+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
	for j in range(V+1):
		# i+1番目を選ぶ場合
		if j-v[i]>=0:
			dp[i+1][j]=min(dp[i+1][j], dp[i][j-v[i]]+w[i])
		# i+1番目を選ばない場合
		dp[i+1][j]=min(dp[i+1][j], dp[i][j])

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans=0
for j in range(V+1):
	if dp[N][j]<=W:
		ans=j

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
N,W = map(int,input().split())
w = [[] for i in range(4)]
w1,v1 = map(int,input().split())
w[0].append(v1)
for i in range(N-1):
    wi,vi = map(int,input().split())
    w[wi-w1].append(vi)
num = []
for i in range(4):
    w[i].sort(reverse= 1)
    w[i] = [0]+list(accumulate(w[i]))
    num.append(len(w[i]))
ans = 0
for n1 in range(num[0]+1):
    for n2 in range(num[1]+1):
        for n3 in range(num[2]+1):
            for n4 in range(num[3]+1):
                wc = w1*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
                if wc <= W:
                    vc = w[0][n1]+w[1][n2]+w[2][n3]+w[3][n4]
                    ans = max(ans,vc)
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,W=LI()
m={}
for i in range(n):
    w,v=LI()
    if w in m:
        m[w].append(v)
    else:
        m[w]=[v]

a=[]
for i,j in m.items():
    sj=sorted(j)[::-1]
    aj=[sum(j)]
    for x in sj:
        aj+=[aj[-1]-x]
    a.append([i,len(j),aj])

cnt0=[0]*len(m.items())
weights=[i for i,j,k in a]

ans=0
sys.setrecursionlimit(10**6)

v=[False]*102**4
def dfs(cnt):
    global ans
    k=sum([cnt[i]*101**i for i in range(len(cnt))])
    if v[k]:continue
    v[k]= True
    tot=0
    V=0
    for i in range(len(cnt)):
        tot+=cnt[i]*weights[i]
        if cnt[i]>a[i][1] or tot>W:
            return
        V+=a[i][2][0]-a[i][2][cnt[i]]
    ans=max(ans,V)
    for i in range(len(cnt)):
        l=[cnt[j] + (1 if i==j else 0) for j in range(len(cnt))]
        dfs(l)

dfs(cnt0)

print(ans)

Submission status: Runtime Error

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*N+1):
            if i>j:
                dp[i][j][k] = dp[i-1][j][k]
                if k>=X[i-1][0]-X[0][0]:
                    dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
            else:
                dp[i][i][k] = dp[i-1][i-1][k-X[i-1][0]+X[0][0]]+X[i-1][1]
cmax = 0
for j in range(1,N+1):
    if W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Runtime Error

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*N+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    if W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Runtime Error

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(301)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(301):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    for k in range(W-j*X[0][0]+1):
        cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Runtime Error

Solution code:
INFTY = 10**8
N,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
w = A[0][0]
C = {i:0 for i in range(4)}
for i in range(N):
    C[A[i][0]-w] += 1
dp = [[[[[-INFTY for _ in range(C[3]+1)] for _ in range(C[2]+1)] for _ in range(C[1]+1)] for _ in range(C[0]+1)] for _ in range(N+1)]
for n in range(N+1):
    dp[n][0][0][0][0] = 0
for n in range(1,N+1):
    for i in range(C[0]+1):
        for j in range(C[1]+1):
            for k in range(C[2]+1):
                for l in range(C[3]+1):
                    dp[n][i][j][k][l] = dp[n-1][i][j][k][l]
                    if A[n-1][0]-w==0:
                        if i>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i-1][j][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==1:
                        if j>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j-1][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==2:
                        if k>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j][k-1][l]+A[n-1][1])
                    elif A[n-1][0]-w==3:
                        if l>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j1][k][l-1]+A[n-1][1])
vmax = 0
for i in range(C[0]+1):
    for j in range(C[1]+1):
        for k in range(C[2]+1):
            for l in range(C[3]+1):
                if (i+j+k+l)*w+j+2*k+3*l<=W:
                    vmax = max(vmax,dp[N][i][j][k][l])
print(vmax)

Submission status: Runtime Error

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
w = A[0][0]
C = {i:0 for i in range(4)}
for i in range(N):
    C[A[i][0]-w] += 1
dp = [[[[[-INFTY for _ in range(C[3]+1)] for _ in range(C[2]+1)] for _ in range(C[1]+1)] for _ in range(C[0]+1)] for _ in range(N+1)]
for n in range(N+1):
    dp[n][0][0][0][0] = 0
dp[1][1][0][0][0] = A[0][1]
for n in range(2,N+1):
    for i in range(C[0]+1):
        for j in range(C[1]+1):
            for k in range(C[2]+1):
                for l in range(C[3]+1):
                    dp[n][i][j][k][l] = dp[n-1][i][j][k][l]
                    if A[n-1][0]-w==0:
                        if i>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i-1][j][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==1:
                        if j>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j-1][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==2:
                        if k>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j][k-1][l]+A[n-1][1])
                    elif A[n-1][0]-w==3:
                        if l>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j1][k][l-1]+A[n-1][1])
vmax = 0
for i in range(C[0]+1):
    for j in range(C[1]+1):
        for k in range(C[2]+1):
            for l in range(C[3]+1):
                if (i+j+k+l)*w+j+2*k+3*l<=W:
                    vmax = max(vmax,dp[N][i][j][k][l])
print(vmax)

Submission status: Runtime Error

Solution code:
n, w = [ int(v) for v in input().split() ]
knapsack = [ [ int(v) for v in input().split() ] for i in range(n) ]

dp_list = [ [ None for i in range(4*n+1) ] for i in range(n+1) ]
dp_list[0][0] = 0
base = knapsack[0][0]


for wi, vi in knapsack:
    wi -= base
    for i in range(n-1,-1,-1):
        for j in range(4*n,-1,-1):
            if 0 <= j-wi < 4*n+1 and 0 <= j < 4*n+1:
                if dp_list[i][j-wi] is not None:
                    if dp_list[i+1][j] is None:
                        dp_list[i+1][j] = dp_list[i][j-wi] + vi
                    else:
                        dp_list[i+1][j] = max(dp_list[i][j-wi] + vi, dp_list[i+1][j])

ans_list = [0]
for i in range(1,n+1):
    l = w - i*base
    for j in range(l+1):
        if dp_list[i][j] is not None:
            ans_list.append(dp_list[i][j])


print(max(ans_list))

Submission status: Runtime Error

Solution code:
n, w = [ int(v) for v in input().split() ]
knapsack = [ [ int(v) for v in input().split() ] for i in range(n) ]

dp_list = [ [ None for i in range(4*n+1) ] for i in range(n+1) ]
dp_list[0][0] = 0
base = knapsack[0][0]


for wi, vi in knapsack:
    wi -= base
    for i in range(n-1,-1,-1):
        for j in range(4*n,-1,-1):
            if 0 <= j-wi < 4*n+1:
                if dp_list[i][j-wi] is not None:
                    if dp_list[i+1][j] is None:
                        dp_list[i+1][j] = dp_list[i][j-wi] + vi
                    else:
                        dp_list[i+1][j] = max(dp_list[i][j-wi] + vi, dp_list[i+1][j])


ans_list = [0]
for i in range(1,n+1):
    l = w-base*i
    for j in range(l+1):
        if dp_list[i][j] is not None:
            ans_list.append(dp_list[i][j])


print(max(ans_list))

Submission status: Runtime Error

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)

for _ in range(n - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0

#print(v_list)

for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if (i * w_0) + (j * (w_0 + 1)) + (k * (w_0 + 2)) + (l * (w_0 + 3)) <= W:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)

Submission status: Runtime Error

Solution code:
# ARC073D - Simple Knapsack (ABC060D)
def knapsack_heavy(W: int, weight: "Array[int]", value: "Array[int]") -> int:
    lim = sum(value)
    dp = [0] + [float("inf")] * lim  # dp[i] := minimum weight at value i
    for w, v in zip(weight, value):
        for cur_v in range(lim, v - 1, -1):
            dp[cur_v] = min(dp[cur_v], dp[cur_v - v] + w)
    ret = max(v for v, w in enumerate(dp) if w <= W)
    return ret


def main():
    N, W, *A = map(int, open(0).read().split())
    weight, value = A[::2], A[1::2]
    ans = knapsack_heavy(W, weight, value)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
a = []
for _ in range(n):
    w_in, v_in = map(int, input().split())
    a.append([w_in, v_in])

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for j in range(w + 1):
    for i in range(n):
        w_in, v_in = a[i]
        if j + w_in <= w:
            dp[i + 1][j + w_in] = max(dp[i + 1][j + w_in], dp[i][j] + v_in)
            if i + 2 <= n:
                dp[i + 2][j + w_in] = max(dp[i + 2][j + w_in], dp[i + 1][j + w_in])
        dp[i + 2][j] = max(dp[i + 2][j], dp[i + 1][j])
print(max([max(d) for d in dp]))

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
wv=[]
for i in range(N):
    a,b=map(int,input().split())
    wv.append((a,b))
if wv[0][0]<300:
    dp=[[0]*(30000+1) for i in range(N+1)]
    for i in range(1,N+1):
        wi,vi=wv[i-1]
        for j in range(1,30000+1):
            dp[i][j]=dp[i-1][j]
            if j-wi<0:
                continue
            dp[i][j]=max(dp[i-1][j-wi]+vi,dp[i][j])
    ans=dp[N][W]
    print(ans)
    quit()
dp=[[0]*(301*101) for i in range(N+1)]
d=wv[0][0]
def change(n):
    return 301*(n//d)+n%d
#if change(W)>301*101:
#    quit()
for i in range(1,N+1):
    wi,vi=wv[i-1]
    z=301+(wi-d)
    for j in range(1,301*101):
        dp[i][j]=dp[i-1][j]
        if j-z<0:
            continue

        dp[i][j]=max(dp[i-1][j-z]+vi,dp[i][j])
ans=dp[N][change(W)]
print(ans)

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
wv=[]
for i in range(N):
    a,b=map(int,input().split())
    wv.append((a,b))
if wv[0][0]<300:
    dp=[[0]*(30000+1) for i in range(N+1)]
    for i in range(1,N+1):
        wi,vi=wv[i-1]
        for j in range(1,30000+1):
            dp[i][j]=dp[i-1][j]
            if j-wi<0:
                continue
            dp[i][j]=max(dp[i-1][j-wi]+vi,dp[i][j])
    ans=dp[N][W]
    print(ans)
    quit()
dp=[[0]*(301*100+1) for i in range(N+1)]
d=wv[0][0]
def change(n):
    return 301*(n//d)+n%d
for i in range(1,N+1):
    wi,vi=wv[i-1]
    z=301+(wi-d)
    for j in range(1,301*100+1):
        dp[i][j]=dp[i-1][j]
        if j-z<0:
            continue

        dp[i][j]=max(dp[i-1][j-z]+vi,dp[i][j])
ans=dp[N][change(W)]
print(ans)

Submission status: Runtime Error

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

n,W = map(int,input().split())
w = [0] * n
v = [0] * n
for i in range(n):
    w[i],v[i] = map(int,input().split())

max_v = sum(v)

dp = [[float("inf")] * (n * max_v + 1) for i in range(n + 1)]

dp[0][0] = 0
for i in range(n):
    for j in range(n * max_v):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j- v[i]] + w[i])
res = 0
for i in range(n * max_v):
    if dp[n][i] <= W:
        res = i

print(res)

Submission status: Runtime Error

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

n,W = map(int,input().split())
w = [0] * n
v = [0] * n
for i in range(n):
    w[i],v[i] = map(int,input().split())

max_v = sum(v)

dp = [[10000000000] * (n * max_v + 1) for i in range(n + 1)]

dp[0][0] = 0
for i in range(n):
    for j in range(n * max_v):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j- v[i]] + w[i])
res = 0
for i in range(n * max_v):
    if dp[n][i] <= W:
        res = i

print(res)

Submission status: Runtime Error

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

n,W = map(int,input().split())
w = [0] * n
v = [0] * n
for i in range(n):
    w[i],v[i] = map(int,input().split())

max_v = sum(v)

dp = [[float("inf")] * (n * max_v + 2) for i in range(n + 2)]

dp[0][0] = 0
for i in range(n):
    for j in range(n * max_v):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j- v[i]] + w[i])
res = 0
for i in range(n * max_v):
    if dp[n][i] <= W:
        res = i

print(res)

Submission status: Runtime Error

Solution code:
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(max(dp)))

Submission status: Runtime Error

Solution code:
import sys, os
import numpy as np

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    N, W = f()
    w = np.zeros((N+1,1), dtype = int)
    v = np.zeros((N+1,1), dtype = int)

    for i in range(1,1+N):
        wtmp, vtmp = f()
        w[i] = wtmp
        v[i] = vtmp

    dp = np.zeros((N+1, N+1, 3*N+1), dtype = int)

    for i in range(1,N+1):
        for j in range(0,i+1):
            for k in range(3*j+1):
                dp[i][j][k] = dp[i-1][j][k]
                if k-(w[i] - w[1]) >=0 and j-1>=0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-(w[i] - w[1])] + v[i])

    ans = 0
    for j in range(N+1):
        for k in range(3*j+1):
            if j*w[1] + k <= W:
                ans = max(ans, dp[N][j][k])

    print(ans)




solve()

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(n)]
dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(w + 1):
        if j < A[i][0]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - A[i][0]] + A[i][1])
            
print(dp[n][w])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
dp = [[-1] * (W + 1) for i in range(N + 1)]

def rec(i, w):
    if dp[i][w] >= 0:
        return dp[i][w]
    #すでに調べたことがあるならばその結果を再利用
    #すでにテーブルに記録してあるので、この時点でreturnして良い
    if i == N:
        res = 0
        # テーブルに記録するまで結果をresに保持しておく
    elif w < A[i][0]:
        res = rec(i + 1, w)
    else:
        res = max(rec(i + 1, w), rec(i + 1, w - A[i][0]) + A[i][1])
    dp[i][w] = res
    # 結果をテーブルに記録する
    return res
    # テーブルに記録したのでreturn

print(rec(0, W))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[-1] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] >= 0:
        ans = memo[i][j]
    elif i == N:
        ans = 0
    elif A[i][0] > j:
        ans = dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
    memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[0] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] != 0:
        ans = memo[i][j]
    elif i == N:
        return 0
    elif A[i][0] > j:
        return dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
        memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[0] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] != 0:
        ans = memo[i][j]
    elif i == N:
        return 0
    elif A[i][0] > j:
        return dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
        memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[0] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] != 0:
        ans = memo[i][j]
    elif i == N:
        return 0
    elif A[i][0] > j:
        return 0
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
        memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
di = dict()
m = 0
for _ in range(n):
  x,y = map(int, input().split())
  if x not in di:
    di[x] = []
  di[x].append(y)
for i in di:
  di[i].sort(reverse=True)
a,b,c,d = di.keys()
for i in range(len(di[a])):
  for j in range(len(di[b])):
    for k in range(len(di[c])):
      for l in range(len(di[d])):
        if i*a + j*b + k*c + l*d <= w:
          m = max(m, sum(di[a][:i+1] + di[b][:j+1] + di[c][:k+1] + di[d][:l+1]))
print(m)