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: Accepted

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):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].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: Accepted

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):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].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: Accepted

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: Accepted

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[3])):
    for j in range(len(x[2])):
        for k in range(len(x[1])):
            #for l in range(len(x[0])):
            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: Accepted

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[3])):
    for j in range(len(x[2])):
        for k in range(len(x[1])):
            for l in range(len(x[0])):
                if i*(w0+3)+j*(w0+2)+k*(w0+1)+l*w0<=w:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][l]
                    ma=max(ma,ma_sub)
                else:
                    break
print(ma)

Submission status: Accepted

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])):
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub=x[0][i]+x[1][j]+x[2][k]+x[3][l]
                    ma=max(ma,ma_sub)
                else:
                    break
print(ma)

Submission status: Accepted

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])):
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub=0
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                    ma=max(ma,ma_sub)
                else:
                    break
print(ma)

Submission status: Accepted

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=0
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                ma=max(ma,ma_sub)
print(ma)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, W = map(int, input().split())

data_list = []
for i in range(N):
    w, v = map(int, input().split())
    data_list.append((w, v))
    
data = defaultdict(int)
data[0] = 0
for w, v in data_list:
    for cw, cv in list(data.items()):
        if cw + w <= W:
            data[cw+w] = max(data[cw+w], cv+v)
            
print(max(data.values()))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n,W = inpm()
    v = [[] for _ in range(4)]
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        v[ wv[0]-w0 ].append(wv[1])
    for i in range(4):
        v[i] = sorted(v[i])
        v[i].reverse()
        vv = [0 for _ in range(len(v[i])+1)]
        for j in range(len(v[i])):
            vv[j+1] = vv[j] + v[i][j]
        v[i] = vv
    ans = 0
    for n1 in range(len(v[0])):
        for n2 in range(len(v[1])):
            for n3 in range(len(v[2])):
                for n4 in range(len(v[3])):
                    if W < w0*(n1+n2+n3+n4) + n2 + n3*2 + n4*3:
                        continue
                    ans = max(ans,v[0][n1]+v[1][n2]+v[2][n3]+v[3][n4])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product, accumulate

N, W = map(int, input().split())
v0, v1, v2, v3 = [None], [], [], []
w0, v0[0] = map(int, input().split())
for i in range(1, N):
    w, v = map(int, input().split())
    if w - w0 == 0:
        v0.append(v)
    elif w - w0 == 1:
        v1.append(v)
    elif w - w0 == 2:
        v2.append(v)
    else:
        v3.append(v)

v0 = sorted(v0, reverse=True)
v1 = sorted(v1, reverse=True)
v2 = sorted(v2, reverse=True)
v3 = sorted(v3, reverse=True)

av0 = [0] + list(accumulate(v0))
av1 = [0] + list(accumulate(v1))
av2 = [0] + list(accumulate(v2))
av3 = [0] + list(accumulate(v3))

ans = 0
for i, j, k, l in product(range(len(v0) + 1), range(len(v1) + 1),
                          range(len(v2) + 1), range(len(v3) + 1)):
    v = av0[i] + av1[j] + av2[k] + av3[l]
    w = w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l
    if w <= W:
        ans = max(v, ans)
print(ans)

Submission status: Accepted

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

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, W = MAP()
WV = []
for i in range(N):
    w, v = MAP()
    WV.append((w, v))

dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = WV[i]
    for k in dp[i].keys():
        dp[i+1][k] = max(dp[i+1][k], dp[i][k])
        if k+w <= W:
            dp[i+1][k+w] = max(dp[i+1][k+w], dp[i][k] + v)
print(max(dp[N].values()))

Submission status: Accepted

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

INF = 10 ** 10
w0 = INF
for w, v in wv:
  w0 = min(w0, w)

for i in range(N):
  wv[i][0] -= w0
#print("wv:", wv)

U = [[] for _ in range(4)]
for w, v in wv:
  U[w].append(v)
  
for i in range(4):
  U[i].sort(reverse = True)
#print("U:", U)

S = [[0] for _ in range(4)]
for i in range(4):
  for u in U[i]:
    S[i].append(S[i][-1] + u)
#print("S", S)

answer = []
for i0 in range(len(S[0])):
  for i1 in range(len(S[1])):
    for i2 in range(len(S[2])):
      for i3 in range(len(S[3])):
        if i1 + i2 * 2 + i3 * 3 + (i0 + i1 + i2 + i3) * w0 <= W:
          answer.append(S[0][i0] + S[1][i1] + S[2][i2] + S[3][i3])
print(max(answer))

Submission status: Accepted

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

w1, v = list(map(int, input().split()))
V = [[] for _ in range(4)]
V[0].append(v)

for _ in range(N-1):
    w, v = list(map(int, input().split()))
    V[w-w1].append(v)

S = []
for vl in V:
    vl.sort(reverse=True)
    s = [0]
    for v in vl:
        s.append(s[-1]+v)
    S.append(s)

ans = 0
for n0, s0 in enumerate(S[0]):
    for n1, s1 in enumerate(S[1]):
        for n2, s2 in enumerate(S[2]):
            for n3, s3 in enumerate(S[3]):
                if n0*w1 + n1*(w1+1) + n2*(w1+2) + n3*(w1+3)<=W:
                    ans = max(ans, s0+s1+s2+s3)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

n, W, *wv = map(int, sys.stdin.read().split())
wv = list(zip(*[iter(wv)] * 2))

def main():
    wv.sort(key=lambda x: x[0])
    min_w = wv[0][0]

    items = [[] for _ in range(4)]
    
    for w, v in wv:
        items[w-min_w].append(v)
    
    for i in range(4):
        items[i].sort(reverse=True)
        items[i].insert(0, 0)
        items[i] = list(accumulate(items[i]))

    res = 0
    s0 = items[0]
    s1 = items[1]
    s2 = items[2]
    s3 = items[3]
    for i in range(len(s0)):
        v0 = s0[i]
        for j in range(len(s1)):
            v1 = s1[j]
            for k in range(len(s2)):
                v2 = s2[k]
                for l in range(len(s3)):
                    v3 = s3[l]
                    if (j + 2*k + 3*l) + min_w * (i+j+k+l) <= W:
                        res = max(res, v0+v1+v2+v3)

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import itertools
n, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
b = []
c = []
d= []
e= []
ans=0

for i in range(n):
    if a[i][0] == a[0][0]:
        b.append(a[i][1])
    elif a[i][0] == a[0][0]+1:
        c.append(a[i][1])
    elif a[i][0] == a[0][0]+2:
        d.append(a[i][1])
    else:
        e.append(a[i][1])

b.sort()
b.reverse()
c.sort()
c.reverse()
d.sort()
d.reverse()
e.sort()
e.reverse()

b = list(itertools.accumulate(b))
c = list(itertools.accumulate(c))
d = list(itertools.accumulate(d))
e = list(itertools.accumulate(e))
b.append(0)
c.append(0)
d.append(0)
e.append(0)


for i in range(len(b)):
    for j in range(len(c)):
        for k in range(len(d)):
            if a[0][0]*i+(a[0][0] +1)*j+(a[0][0] +2)*k>w:
                break
            else:
                x=(w-(a[0][0]*i+(a[0][0] +1)*j+(a[0][0] +2)*k))//(a[0][0]+3)
                ans=max(ans,b[i-1]+c[j-1]+d[k-1]+e[min(x-1,len(e)-1)])
print(ans)

Submission status: Accepted

Solution code:
import sys

n, W = map(int, sys.stdin.readline().split())
wv = map(int, sys.stdin.read().split())

wv = sorted(zip(*[wv] * 2))
min_w = wv[0][0]
W2 = 4 * n

def main():
    dp = [[[0] * (W2 + 1) for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(n):
        w, v = wv[i]
        w -= min_w - 1
        for j in range(1, i+2):
            for k in range(W2 + 1):
                if k + (min_w - 1) * j > W:
                    break
                dp[i+1][j][k] = dp[i][j][k]
                if k >= w:
                    dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-w] + v)

    res = 0
    for j in dp[n]:
        res = max(res, max(j))

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W//A[0][0] > 100:
        print(sum(list(zip(*A))[1]))
        exit()
    if W%A[0][0] >= 300:
        W = W//A[0][0]*300+299
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

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

print(DP[N][W])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, product
from operator import itemgetter
read = sys.stdin.read

N, W, *wv = map(int, read().split())
w1 = wv[0]
V = [[0] for _ in range(4)]

for w, v in sorted(zip(*[iter(wv)] * 2), key=itemgetter(1), reverse=True):
    V[w - w1].append(v)


V = list(map(list, map(accumulate, V)))
n = [len(V[i]) for i in range(4)]
answer = 0
for a, b, c in product(range(n[0]), range(n[1]), range(n[2])):
    tmp = b + c * 2 + (a + b + c) * w1
    if tmp > W:
        continue

    d = min(n[3] - 1, (W - tmp) // (w1 + 3))
    v = V[0][a] + V[1][b] + V[2][c] + V[3][d]
    if v > answer:
        answer = v

print(answer)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, product
from operator import itemgetter
read = sys.stdin.read

N, W, *wv = map(int, read().split())
w1 = wv[0]
V = [[0] for _ in range(4)]

for w, v in sorted(zip(*[iter(wv)] * 2), key=itemgetter(1), reverse=True):
    V[w - w1].append(v)


V = list(map(list, map(accumulate, V)))
n = [len(V[i]) for i in range(4)]
answer = 0
for a, b, c, d in product(range(n[0]), range(n[1]), range(n[2]), range(n[3])):
    if b + c * 2 + d * 3 + (a + b + c + d) * w1 > W:
        continue

    v = V[0][a] + V[1][b] + V[2][c] + V[3][d]
    if v > answer:
        answer = v

print(answer)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w0, v0 = map(int, input().split())
X = [[] for _ in range(4)]
X[0].append(v0)
for _ in range(N-1):
    w, v = map(int, input().split())
    X[w-w0].append(v)

X = [[0] + sorted(x)[::-1] for x in X]
for i in range(4):
    for j in range(1, len(X[i])):
        X[i][j] += X[i][j-1]
ma = 0
for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            l = min(N-i-j-k, (W - (w0 * i + (w0+1) * j + (w0+2) * k)) // (w0+3))
            if l < 0: continue
            if i < len(X[0]) and j < len(X[1]) and k < len(X[2]) and l < len(X[3]):
                ma = max(ma, X[0][i] + X[1][j] + X[2][k] + X[3][l])
print(ma)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    value = {}
    value[w[0]] = []
    value[w[0]+1] = []
    value[w[0]+2] = []
    value[w[0]+3] = []
    accum = {}
    answer = 0

    for i in range(N):
        value[w[i]].append(v[i])

    len0 = len(value[w[0]])
    len1 = len(value[w[0]+1])
    len2 = len(value[w[0]+2])
    len3 = len(value[w[0]+3])

    for i in range(4):
        value[w[0]+i].sort(reverse = True)
        accum[w[0]+i] = [0]+list(accumulate(value[w[0]+i]))

    for i in range(len0+1):
        for j in range(len1+1):
            for k in range(len2+1):
                for l in range(len3+1):
                    if i*w[0]+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) <= W:
                        answer = max(accum[w[0]][i]+accum[w[0]+1][j]+accum[w[0]+2][k]+accum[w[0]+3][l],answer)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
from collections import defaultdict
WD=[list(map(int,input().split())) for _ in range(n)]
d=defaultdict(int)
d[0]=0
for w,v in WD:
    for i ,j in d.copy().items():
        if i+w <=W:
            d[w+i]=max(d[w+i],j+v)

print(max(d.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate
N, W = map(int, input().split())
w = [0] * N; v = [0] * N
d = defaultdict(list)
for i in range(N):
    w[i], v[i] = map(int, input().split())
    d[w[i]].append(v[i])

for i in range(4):
    d[w[0]+i].sort(reverse=True)
    d[w[0]+i].insert(0, 0)
    d[w[0]+i] = list(accumulate(d[w[0]+i]))


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

Submission status: Accepted

Solution code:
from operator import itemgetter

N,W = map(int, input().split())
List = [[int(l) for l in input().split()] for _ in range(N)]

num = [0]*4
w0 = List[0][0]
for i in range(N):
    num[List[i][0]-w0] += 1
    
List.sort(reverse=True, key=itemgetter(1))
L = []
for i in range(N):
    if List[i][0] == w0:
        L.append(List[i])
for i in range(N):
    if List[i][0] == w0+1:
        L.append(List[i])
for i in range(N):
    if List[i][0] == w0+2:
        L.append(List[i])
for i in range(N):
    if List[i][0] == w0+3:
        L.append(List[i])
        
prev = w0
for i in range(1, N):
    if L[i][0] == prev:
        L[i][1] += L[i-1][1]
    else:
        prev += 1
        
ans = 0
for i in range(-1, num[0]):
    wi = (i+1)*w0
    ci = 0
    if i >= 0:
        if wi > W:
            break
        ci += L[i][1]
    for j in range(-1, num[1]):
        wj = (j+1)*(w0+1)
        cj = 0
        if j >= 0:
            if wi+wj > W:
                break
            cj += L[j+num[0]][1]
        for k in range(-1, num[2]):
            wk = (k+1)*(w0+2)
            ck = 0
            if k >= 0:
                if wi+wj+wk > W:
                    break
                ck += L[k+num[0]+num[1]][1]
            for l in range(-1, num[3]):
                wl = (l+1)*(w0+3)
                cl = 0
                if l >= 0:
                    if wi+wj+wk+wl > W:
                        break
                    cl += L[l+num[0]+num[1]+num[2]][1]
                ans = max(ans, ci+cj+ck+cl)
            
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w0,v=map(int,input().split())
    V=[[] for _ in range(4)]
    V[0].append(v)
    for _ in range(n-1):
        w,v=map(int,input().split())
        V[w-w0].append(v)
    for i in range(4):
        V[i].sort(reverse=1)
        V[i].insert(0,0)
        for j in range(len(V[i])-1):
            V[i][j+1]+=V[i][j]

    ans=0
    from itertools import product
    for a,b,c,d in product(range(len(V[0])),range(len(V[1])),range(len(V[2])),range(len(V[3]))):
        v=V[0][a]+V[1][b]+V[2][c]+V[3][d]
        if(a*w0+b*(w0+1)+c*(w0+2)+d*(w0+3)<=W): ans=max(ans,v)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w0,v=map(int,input().split())
    V=[[] for _ in range(4)]
    V[0].append(v)
    for _ in range(n-1):
        w,v=map(int,input().split())
        V[w-w0].append(v)
    for i in range(4):
        V[i].sort(reverse=1)
        for j in range(len(V[i])-1):
            V[i][j+1]+=V[i][j]
    for i in range(4):
        V[i].insert(0,0)

    ans=0
    from itertools import product
    for a,b,c,d in product(range(len(V[0])),range(len(V[1])),range(len(V[2])),range(len(V[3]))):
        v=V[0][a]+V[1][b]+V[2][c]+V[3][d]
        if(a*w0+b*(w0+1)+c*(w0+2)+d*(w0+3)<=W): ans=max(ans,v)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import defaultdict
def resolve():
    n,W=map(int,input().split())
    WV=[tuple(map(int,input().split())) for _ in range(n)]

    weight=set()
    for i in range(n+1):
        if(WV[0][0]*i>W): break
        for j in range(3*i+1):
            if(WV[0][0]*i+j>W): break
            weight.add(WV[0][0]*i+j)
    weight=sorted(weight)

    dp=defaultdict(int)
    for i in range(n):
        ndp=defaultdict(int)
        w,v=WV[i]
        for key in weight:
            ndp[key]=max(ndp[key],dp[key])
            if(key+w<=W): ndp[key+w]=max(ndp[key+w],dp[key]+v)
        dp=ndp

    print(max(dp.values()))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import defaultdict
def resolve():
    n,W=map(int,input().split())
    WV=[tuple(map(int,input().split())) for _ in range(n)]

    weight=set()
    for i in range(n+1):
        for j in range(3*i+1):
            if(WV[0][0]*i+j>W): continue
            weight.add(WV[0][0]*i+j)
    weight=sorted(weight)

    dp=defaultdict(int)
    for i in range(n):
        ndp=defaultdict(int)
        w,v=WV[i]
        for key in weight:
            ndp[key]=max(ndp[key],dp[key])
            if(key+w<=W): ndp[key+w]=max(ndp[key+w],dp[key]+v)
        dp=ndp

    ans=0
    for key in weight:
        ans=max(ans,dp[key])
    print(ans)
resolve()

Submission status: Accepted

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

import collections
w_v_pairs = collections.defaultdict(list)
for _ in range(N):
    w, v = map(int, input().split(' '))
    w_v_pairs[w].append(v)


for w in w_v_pairs.keys():
    w_v_pairs[w].sort(reverse=True)

ans = 0
weights = list(w_v_pairs.keys())
buf = [(W, 0, 0)]
while len(buf) != 0:
    rest_w, i_weights, v = buf.pop()
    ans = max(ans, v)

    if i_weights < len(weights):
        buf.append((rest_w, i_weights + 1, v))

        w = weights[i_weights]
        values = w_v_pairs[w]
        j = 0
        while j < len(values):
            rest_w -= w
            if rest_w < 0:
                break
            else:
                v += values[j]
                buf.append((rest_w, i_weights+1, v))
                j += 1



# print(w_v_pairs)
print(ans)

Submission status: Accepted

Solution code:
# atcoder : python3 (3.4.3)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7

# main
from itertools import accumulate
N,W = map(int,input().split())
V = [[] for _ in range(4)]
w0 = None
for i in range(N):
    w,v = map(int,input().split())
    if i==0:
        w0 = w
        V[0].append(v)
    else:
        V[w-w0].append(v)

for i in range(4):
    V[i].sort(reverse=True)

S = [[] for _ in range(4)]
for i in range(4):
    S[i] = [0] + list(accumulate(V[i]))

ans = 0
for i0 in range(len(S[0])):
    for i1 in range(len(S[1])):
        for i2 in range(len(S[2])):
            for i3 in range(len(S[3])):
                if w0*i0 + (w0+1)*i1 + (w0+2)*i2 + (w0+3)*i3 <= W:
                    ans = max(ans, S[0][i0] + S[1][i1] + S[2][i2] + S[3][i3])

print(ans)

Submission status: Accepted

Solution code:
#w1<=wi<w1+3
from itertools import product
n,w_max = map(int, input().split( ))
w = {}
w1,v1 = map(int, input().split( ))
w[w1] = [v1]
w2 = w1+1
w3 =w2+1
w4 = w3+1
w[w2] = [0]
w[w3] = [0]
w[w4] = [0]
for i in range(n-1):
    wi,vi=map(int, input().split( ))
    w[wi].append(vi)

for wi in w:
    w[wi].sort(reverse = True)
#print(w)
ans = 0
l1 = len(w[w1])+1
l2 = len(w[w2])+1
l3 = len(w[w3])+1
l4 = len(w[w4])+1
for i1,i2,i3,i4 in product(range(l1),range(l2),range(l3),range(l4)):
    if w1*i1+w2*i2+w3*i3+w4*i4<=w_max:
        ans = max(ans,sum(w[w1][:i1])+sum(w[w2][:i2])+sum(w[w3][:i3])+sum(w[w4][:i4]))###

print(ans)

Submission status: Accepted

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

dp = [[[0 for k in range(3*N+1)] for j in range(N+1)] for i in range(N+1)]

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

Submission status: Accepted

Solution code:
#ABC060D
N, W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in range(N)]
A = WV[0][0]
B = A + 1
C = A + 2
D = A + 3

AA = []
BB = []
CC = []
DD = []

for wv in WV:
  if wv[0] == A:
    AA.append(wv[1])
  elif wv[0] == B:
    BB.append(wv[1])
  elif wv[0] == C:
    CC.append(wv[1])
  else:
    DD.append(wv[1])

AA = sorted(AA)[::-1]
BB = sorted(BB)[::-1]
CC = sorted(CC)[::-1]
DD = sorted(DD)[::-1]

ans = 0
for a in range(N+1):
  for b in range(N+1-a):
    for c in range(N+1-a-b):
      for d in range(N+1-a-b-c):
        if a > len(AA) or b > len(BB) or c > len(CC) or d > len(DD):
          continue
        if A * a + B * b + C * c + D * d > W:
          continue
        tmp = sum(AA[:a])+sum(BB[:b])+sum(CC[:c])+sum(DD[:d])
        ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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

if N==1:
  print(v1)
  exit()

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):
    for i3 in range(lens[w1+2]+1):
      if W-i1*w1-i2*(w1+1)-i3*(w1+2) < 0: continue
      i4 = (W-i1*w1-i2*(w1+1)-i3*(w1+2))//(w1+3)
      ans = max(ans, sum(items[w1][:i1])+sum(items[w1+1][:i2])+sum(items[w1+2][:i3])+sum(items[w1+3][:i4]))
print(ans)