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:
import sys
readline = sys.stdin.buffer.readline
N,W = map(int,readline().split())
wv = [list(map(int,readline().split())) for i in range(N)]

#i:N,j:W,value:value
dp = [[0]*(W+1) for i in range(N+1)]

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

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

Submission status: Runtime Error

Solution code:
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,0,-1):
    for j in range(W,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M,-1,-1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)

Submission status: Runtime Error

Solution code:
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,-1,-1):
    for j in range(W,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M,-1,-1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)

Submission status: Runtime Error

Solution code:
n,w=map(int, input().split())
lim = min(w,10**5)
dp = [0] * (lim+1)
items = []
mod = 10**5
for _ in range(n):
    ww,v = map(int, input().split())
    items.append((ww,v))
    if ww > mod:
        continue
    for i in range(ww,lim+1)[::-1]:
        # print(i)
        if dp[i-ww] + v > dp[i]:
            dp[i] = dp[i-ww] + v
    # print(dp)
if w <= 10**5:
    print(dp[-1])
    exit()
ll = w-mod
dd = [0] * (ll+1)
for ww,v in items:
    if ww <= mod:
        continue
    u = ww % mod
    for i in range(u,ll+1)[::-1]:
        if dd[i-u] + v > dd[i]:
            dd[i] = dd[i-u] + v
    # print(dp)
print(dp[-1] + dd[-1])

Submission status: Runtime Error

Solution code:
n,w=map(int, input().split())
dp = [0] * (w+1)
ans = 0
for _ in range(n):
    ww,v = map(int, input().split())
    for i in range(ww,w+1)[::-1]:
        if dp[i-ww] + v > dp[i]:
            dp[i] = dp[i-ww] + v
            if ans < dp[i]:
                ans = dp[i]
    # print(dp)
print(ans)

Submission status: Runtime Error

Solution code:
4 1
10 100
10 100
10 100
10 100

Submission status: Runtime Error

Solution code:
def solve():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    base_weight = wv[0][0]
    # sum_w = sum(map(lambda x:x[0], wv))
    
    if base_weight > W:
        print(0)
        return
    
    wv_ = [[wv[i][0]-base_weight, wv[i][1]] for i in range(N)]
    dp_W = 3*N
    if base_weight > 3:
        dp_W = 3*N
        if (base_weight+3)*N > W:
            dp_W = 3*(W//base_weight)
        
        dp_W = sum(map(lambda x:x[0], wv))
        dp_table = [[0]*(dp_W+1) for _ in range(N+1)]
        # dp[i][j] := i番目の品物を使ってw[0]+jの重さ以下の価値最大化テーブル
        for i in range(0,N):
            for j in range(0,dp_W+1):
                if j >= (3*i)+wv_[i][0]:
                    dp_table[i+1][j] = max(dp_table[i][j], dp_table[i][j-( (3*i)+wv_[i][0] )]+wv[i][1])
                else:
                    dp_table[i+1][j] = dp_table[i][j]
    else:
        dp_W = min(sum(map(lambda x:x[0], wv)),W)
        dp_table = [[0]*(dp_W+1) for _ in range(N+1)]
        # dp[i][j] := i番目の品物を使ってjの重さ以下の価値最大化テーブル
        for i in range(0,N):
            for j in range(0,dp_W+1):
                if j >= wv[i][0]:
                    dp_table[i+1][j] = max(dp_table[i][j], dp_table[i][j-wv[i][0]]+wv[i][1])
                else:
                    dp_table[i+1][j] = dp_table[i][j]
        # if sum_w > W:
    
    # print(dp_table)
    print(dp_table[N][dp_W])
    
solve()

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w1,v = map(int,input().split())
d = [[-v],[],[],[]]
for i in range(N-1):
    w,v = map(int,input().split())
    x = w - w1
    d[x].append(-v)
d[0].sort()
n0 = len(d[0])
d[1].sort()
n1 = len(d[1])
d[2].sort()
n2 = len(d[2])
d[3].sort()
n3 = len(d[3])
d = [[[[0 for i in range(n3+1)] for j in range(n2+1)] for k in range(n1+1)] for l in range(n0+1)]
for i in range(n0):
    s = sum(d[0][:i])
    for j in range(n1):
        s += sum(d[1][:j])
        for k in range(n2):
            s += sum(d[2][:k])
            for l in range(n3):
                s += sum(d[3][:l])
                s = -s
                x = w1*(i+j+k+l) + j + 2*k + 3*l
                if x <= W:
                    d[i][j][k][l] = s
ans = 0
for i in range(n0):
    for j in range(n1):
        for k in range(n2):
            for l in range(n3):
                x = d[i][j][k][l]
                ans = max(ans,x)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000*5000)
import numpy as np
N,W = map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  
# メモ化テーブル  
memo = np.zeros((N+1, W+1), dtype=int)  
def rec(n, uplimit_w):  
  # 既に記録済みならその値を返すだけ  
  if memo[n, uplimit_w] > 0:  
    return memo[n, uplimit_w]  
  ans = 0  
  if n == N:  
    return 0  
  # n番目の品物を使えない場合 -> (n+1)番目の品物を使った結果と同じ  
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  
  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    memo[n, uplimit_w] = ans  
    return ans  
print(rec(0, W))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500*500)
import numpy as np
N,W = map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  
# メモ化テーブル  
memo = np.zeros((N+1, W+1), dtype=int)  
def rec(n, uplimit_w):  
  # 既に記録済みならその値を返すだけ  
  if memo[n, uplimit_w] > 0:  
    return memo[n, uplimit_w]  
  ans = 0  
  if n == N:  
    return 0  
  # n番目の品物を使えない場合 -> (n+1)番目の品物を使った結果と同じ  
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  
  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    memo[n, uplimit_w] = ans  
    return ans  
print(rec(0, W))

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  
# メモ化テーブル  
memo = np.zeros((N+1, W+1), dtype=int)  
def rec(n, uplimit_w):  
  # 既に記録済みならその値を返すだけ  
  if memo[n, uplimit_w] > 0:  
    return memo[n, uplimit_w]  
  ans = 0  
  if n == N:  
    return 0  
  # n番目の品物を使えない場合 -> (n+1)番目の品物を使った結果と同じ  
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  
  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    memo[n, uplimit_w] = ans  
    return ans  
print(rec(0, W))

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  

# メモ化テーブル  
memo = np.zeros((N+1, W+1), dtype=int)  

def rec(n, uplimit_w):  

  # 既に記録済みならその値を返すだけ  
  if memo[n, uplimit_w] > 0:  
    return memo[n, uplimit_w]  

  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合 -> (n+1)番目の品物を使った結果と同じ  
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  

    memo[n, uplimit_w] = ans  
    return ans  

print(rec(0, W))

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  

# メモ化テーブル  
memo = np.zeros((N+1, W+1), dtype=int)  

def rec(n, uplimit_w):  

  # 既に記録済みならその値を返すだけ  
  if memo[n, uplimit_w] > 0:  
    return memo[n, uplimit_w]  

  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合 -> (n+1)番目の品物を使った結果と同じ  
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  

    memo[n, uplimit_w] = ans  
    return ans  

def solve():  
  print(rec(0, W))  

def main():  
  solve()  

if __name__ == "__main__":  
  main()

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  

# メモ化テーブル  
#memo = np.zeros((N+1, W+1), dtype=int)  

def rec(n, uplimit_w):  

  # 既に記録済みならその値を返すだけ  
#  if memo[n, uplimit_w] > 0:  
#    return memo[n, uplimit_w]  

  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合 -> (n+1)番目の品物を使った結果と同じ  
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  

#    memo[n, uplimit_w] = ans  
    return ans  

def solve():  
  print(rec(0, W))  

def main():  
  solve()  

if __name__ == "__main__":  
  main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, lim = MI()
    ww = []
    vv = []
    for _ in range(n):
        w, v = MI()
        ww.append(w)
        vv.append(v)
    w0=ww[0]
    # dp[i][j]…荷物の個数がiで、端数の合計がjのときの価値の最大値
    dp=[[0]*(3*n+1) for _ in range(n+1)]
    for w,v in zip(ww,vv):
        for i in range(n,0,-1):
            for j in range(lim-i*w0,-1,-1):
                nj=j-(w-w0)
                if nj<0:continue
                dp[i][j]=max(dp[i][j],dp[i-1][nj]+v)
    #p2D(dp)
    print(max(max(row) for row in dp))

main()

Submission status: Runtime Error

Solution code:
# 典型ナップザックと思うと解けない（配列がとんでもないことになる）
# 制約から考えると重さは4種類で合計最大100個なので「どの重さがいくつあるか」で探索できる

n, w = map(int, input().split())
weight = {}
first = list(map(int, input().split()))
for i in range(first[0], first[0] + 4):
    weight[i] = []
weight[first[0]].append(first[1])
for _ in range(n - 1):
    w, v = map(int, input().split())
    weight[w].append(v)


weight = dict([[k, sorted(v, reverse=True)] for k, v in weight.items()])
keys = list(weight.keys())

ans = 0
for i in range(len(weight[keys[0]])):
    for j in range(len(weight[keys[1]])):
        for k in range(len(weight[keys[2]])):
            for l in range(len(weight[keys[3]])):
                if i * keys[0] + j * keys[1] + k * keys[2] + j * keys[3] <= w:
                    ans = max(
                        ans,
                        weight[keys[0]][:i]
                        + weight[keys[1]][:j]
                        + weight[keys[2][:k]]
                        + weight[3][:l],
                    )

print(ans)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    w_sub-=w0
    x[W_sub].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2)):
        for k in range(l1):
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
            ma=max(ma,ma_sub)
print(ma)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)
#print(x)
ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            #for l in range(len(x[3])):
            ma_sub=x[0][i]+x[1][j]+x[2][k]+x[3][w-(i*w0+j*(w0+1)+k*(w0+2))//(w0+3)]
            ma=max(ma,ma_sub)
print(ma)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
s=0
for i in range(n):
    s+=wv[i][1]
x=[0]*(w+1)
for i in range(n):
    x_sub=[0]*(w+1)
    if wv[i][0]<w+1:
        x_sub[wv[i][0]]=wv[i][1]
    for j in range(1,w+1):
        if x[j]!=0 and j+wv[i][0]<w+1:
            x_sub[j+wv[i][0]]=x[j]+wv[i][1]
    for j in range(1,w+1):
        x[j]=max(x_sub[j],x[j])
print(max(x))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.read

N, W, *wv = map(int, read().split())
dp = np.zeros((W + 1, N + 1), np.int64)
idx = 1

for w, v in zip(*[iter(wv)] * 2):
    dp[:, idx] = dp[:, idx - 1]
    if w <= W:
        dp[w:, idx] = np.maximum(dp[w:, idx], dp[:-w, idx] + v)
    idx += 1

print(dp[-1, -1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.read

N, W, *wv = map(int, read().split())
dp = np.zeros((W + 1, N + 1), np.int64)
idx = 1

for w, v in zip(*[iter(wv)] * 2):
    if w > W:
        continue

    dp[:, idx] = dp[:, idx - 1]
    dp[w:, idx] = np.maximum(dp[w:, idx], dp[:-w, idx] + v)
    idx += 1

print(dp[-1, -1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.read

N, W, *wv = map(int, read().split())
dp = np.zeros((W + 1, N + 1), np.int64)
idx = 1

for w, v in zip(*[iter(wv)] * 2):
    if w > W:
        continue

    dp[:, idx] = dp[:, idx - 1]
    dp[w:, idx] = np.maximum(dp[w:, idx], dp[:W - w + 1, idx] + v)
    idx += 1

print(dp[-1, -1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.read

N, W, *wv = map(int, read().split())
dp = np.zeros((W + 1, N + 1), np.int64)
idx = 1

for w, v in zip(*[iter(wv)] * 2):
    dp[:, idx] = dp[:, idx - 1]
    dp[w:, idx] = np.maximum(dp[w:, idx], dp[:W - w + 1, idx] + v)
    idx += 1

print(dp[-1, -1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())

w, v = [], []
for i in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)
# for i in range(N):
#     wi, vi = map(int, input().split())
#     if i == 0:
#         w1 = wi
#     w.append(wi-w1)
#     v.append(vi)

# W -= w1*N

# dp[i+1][j]: 重さjまで入れていい状況で, i番目まで最適に保証された状態.
dp = [[0]*(W+1) for i in range(N+1)]

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())

w, v = [], []
for i in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

N,W = map(int,input().split())
wv = []
for i in range(N):
  x,y = map(int,input().split())
  wv.append([x,y])
print(wv)


  
dp = [[0 for i in range(N+10)]for j in range(W+10)]

for i in range(1,N+1):
  for wi in range(1,W+1):
    if wi>=wv[i-1][0]:
      dp[i][wi] = max(dp[i-1][wi-wv[i-1][0]]+wv[i-1][1],dp[i-1][wi])
    else:
      dp[i][wi] = dp[i-1][wi]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  x,y = [int(i) for i in input().split()]
  w.append(x)
  v.append(y)
  
dp = [[0 for i in range(N+1000)]for j in range(W+1000)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  x,y = [int(i) for i in input().split()]
  w.append(x)
  v.append(y)
  
dp = [[0 for i in range(N+10)]for j in range(W+10)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
#ABC060D
N, W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in range(N)]
dp = [[0] * (N+10) for _ in range(W+10)]

#DPループ
for i in range(N):
    for w in range(W+1):
        if w >= WV[i][0]:
            dp[i+1][w] = max(dp[i][w-WV[i][0]] + WV[i][1],dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
#print(*dp,sep="\n")
print(dp[N][W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w1,v1 = map(int,input().split())
items = {w: [] for w in range(w1,w1+3)}
items[w1].append(v1)
for _ in range(N-1):
  w,v = map(int,input().split())
  items[w].append(v)

lens = {}
for key in sorted(items.keys()):
  items[key].sort(reverse=True)
  lens[key] = len(items[key])

ans = -float('inf')
for i1 in range(lens[w1]+1):
  for i2 in range(lens[w1+1]+1):
    if W-i1*w1-i2*(w1+1) < 0: continue
    i3 = (W-i1*w1-i2*(w1+1))//(w1+2)
    ans = max(ans, sum(items[w1][:i1])+sum(items[w1+1][:i2])+sum(items[w1+2][:i3]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    if wv[0][0] > w:
        print(0)
    else:
        dp = [0] * (10 * 3)
        dp[0] = wv[0][1]
        for i in range(1, len(wv)):
            for j in range(len(dp)-1, -1, -1):
                if j + wv[i][0] <= w:
                    dp[j+wv[i][0] - wv[0][0]] = max(dp[j+wv[i][0] - wv[0][0]], dp[j - wv[0][0]] + wv[i][1])
        print(max(dp))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n, W = [int(x) for x in input().split()]
weight = []
value = []
for i in range(n):
    wi, vi = [int(x) for x in input().split()]
    weight.append(wi)
    value.append(vi)

dp = [[0] * (W+1)] * (n+1)

for i in range(n):
    for w in range(W+1):
        if w >= weight[i]:
            dp[i+1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
   
ans = dp[n][W]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N,W=map(int,input().split())
a=[];b=[];c=[];d=[]
w1,v=map(int,input().split())
w2=w1+1;w3=w2+1;w4=w3+1
a.append(v)
for i in range(N-1):
    w,v=map(int,input().split())
    if w==w1:
        a.append(v)
    elif w==w2:
        b.append(v)
    elif w==w3:
        c.append(v)
    elif w==w4:
        d.append(v)
print(a,b,c,d)

a.sort();b.sort();c.sort();d.sort()

pa=deque(a);pb=deque(b);pc=deque(c);pd=deque(d)
qa=deque();qb=deque();qc=deque();qd=deque()

bw=0
while pa and bw+w1<=W:
    qa.appendleft(pa.pop())
    bw+=w1
while pb and bw+w2<=W:
    qb.appendleft(pb.pop())
    bw+=w2
while qa and pb and bw+1<=W and qa[0]<pb[-1]:
    qa.popleft()
    qb.appendleft(pb.pop())
    bw+=1
while pc and bw+w3<=W:
    qc.appendleft(pc.pop())
    bw+=w3
while pc:
    if qa and bw+2<=W and (not qb or qa[0]<=qb[0]) and qa[0]<pc[-1]:
        qa.popleft()
        qc.appendleft(pc.pop())
        bw+=2
    elif qb and bw+1<=W and qb[0]<pc[-1]:
        qb.popleft()
        qc.appendleft(pc.pop())
        bw+=1
while pd and bw+w4<=W:
    qd.appendleft(pd.pop())
    bw+=w4
while pd:
    if qa and bw+3<=W and (not qb or qa[0]<=qb[0]) and (not qc or qa[0]<=qc[0]) and qa[0]<pd[-1]:
        qa.popleft()
        qd.appendleft(pd.pop())
        bw+=3
    elif qb and bw+2<=W and (not qc or qb[0]<=qc[0]) and qb[0]<pd[-1]:
        qb.popleft()
        qd.appendleft(pd.pop())
        bw+=2
    elif qc and bw+1<=W and qc[0]<pd[-1]:
        qc.popleft()
        qd.appendleft(pd.pop())
        bw+=1

print(sum(qa+qb+qc+qd))

Submission status: Runtime Error

Solution code:
import numpy as np

n, w = map(int, input().split())
l = []
for i in range(n):
    l.append(list(map(int, input().split())))
# print(l)

dp = np.zeros((n + 1, w + 1))

for i in range(n):
    for w in range(w + 1):
        if w >= l[i][0]:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - l[i][0]] + l[i][1])
        else:
            dp[i + 1][w] = dp[i][w]
# print(dp)
print(int(dp[n][w]))

Submission status: Runtime Error

Solution code:
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
def cmb(n, r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)
 
def main():
    n,W=map(int,input().split())
    d=defaultdict(int)
    d[0]=0
    for i in range(n):
        w,v=map(int,input().split())
        for k,j in d.items():
            if k+w<=W:
                d[k+w]=max(d[k+w],j+v)
#    print(d)
    print(max(d.values()))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())

WV = [0]*N
for i in range(N):
  w, v = map(int, input().split())
  WV[i] = w, v
#WV.sort()
dp = [[0]*(W+1) for i in range(N+1)]

for c in range(1, N+1):
  wv = WV[c-1] 
  for w in range(W+1):
    if w < wv[0]:
      dp[c][w] = dp[c-1][w]
    else:
      dp[c][w] = max(dp[c-1][w -wv[0]] + wv[1], dp[c-1][w])
print(dp[-1][-1])

#for i in range(1,N+1):  print(WV[i-1],*dp[i],sep="\t")

Submission status: Runtime Error

Solution code:
N,W,*l = map(int,open(0).read().split())
wl = l[::2]
vl = l[1::2]
M = N*max(vl)
INF = float("inf")
dp = [[INF]*(M+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
	w,v = wl[i],vl[i]
	for j in range(M+1):
		if j >= v:
			dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
		else:
			dp[i+1][j] = dp[i][j]

ans=0
for val,wei in enumerate(dp[-1]):
	if wei <= W:
		ans = max(ans,val)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    MAX_ = (wv[0][0] + 3) * N

    dp = np.zeros((N+1, min(W, MAX_) + 1), dtype=int)

    for i in range(1, N+1):
        w, v = wv[i-1]
        dp[i] = dp[i-1]
        dp[i, w:] = np.maximum(dp[i, w:], dp[i, :-w] + v)
    # print(dp)
    print(dp[-1][-1])
    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,W=map(int,input().split())
dp=[0]*(W+1)
for _ in [0]*n:
    w,v=map(int,input().split())
    for i in range(W,w-1,-1):
        dp[i]=max(dp[i],dp[i-w]+v)
print(dp[-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, w = LI()
weight, value = list(zip(*LIR(n)))
dp = (w + 1) * [0]
for i in range(n):
    for j in range(w, weight[i]-1, -1):
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])



print(dp[-1])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())
    
dp = [[0 for i in range(W+1)] for j in range(N)]

#荷物を1つだけ入れた状態で、各許容重量の最大値を初期値として持たせる
for i in range(N):
    dp[i][w[i]] = v[i]

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

print(dp[N-1][W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())
    
dp = [[0 for i in range(W+1)] for j in range(N)]

#荷物を1つだけ入れた状態で、各許容重量の最大値を初期値として持たせる
for i in range(w[0],W+1):
    dp[0][i] = v[0]

for i in range(1,N):
    for k in range(1,w[i]+1):
        dp[i][k] = dp[i-1][k]
        for j in range(w[i],W+1):
            dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-w[i]]+v[i])
'''
for i in range(N):
    print(dp[i])
'''

print(dp[N-1][W])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return

#C
def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)
    return

#D
def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * ((3 * n + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * n, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(W // minw, 0, -1):
                for k in range(W % minw , w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k - w] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + W % minw + 1]))
    return

#Solve
if __name__ == '__main__':
    D()