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.

Solution (Python):


"""
参考：https://img.atcoder.jp/arc073/editorial.pdf
　　　https://ei1333.hateblo.jp/entry/2017/05/01/004235
　　　https://atcoder.jp/contests/abc060/submissions/3782609
・公式解
・とりあえず累積和なしでやってみる。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

N, W = map(int, input().split())
wN = [0] * N
vN = [[] for i in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        offset = w
    vN[w-offset].append(v)


for i in range(4):
    
    vN[i] = [0] + sorted(vN[i], reverse=True)

ans = 0
for i in range(len(vN[0])):
    for j in range(len(vN[1])):
        for k in range(len(vN[2])):
            for l in range(len(vN[3])):
                
                if offset * i + (offset+1) * j + (offset+2) * k + (offset+3) * l > W:
                    continue
                ans = max(sum(vN[0][:i+1]) + sum(vN[1][:j+1]) + sum(vN[2][:k+1])+ sum(vN[3][:l+1]), ans)
print(ans)

Solution (Python):


"""
・メモ化再帰
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = map(int, input().split())


memo = [defaultdict(lambda: -1) for i in range(N+1)]

def dfs(cur, wei):
    
    if memo[cur][wei] != -1:
        return memo[cur][wei]
    
    if cur == N:
        res = 0
    
    elif wei >= wN[cur]:
        res = max(dfs(cur+1, wei-wN[cur]) + vN[cur], dfs(cur+1, wei))
    
    else:
        res = dfs(cur+1, wei)
    
    memo[cur][wei] = res
    return res

print(dfs(0, W))

Solution (Python):
from itertools import accumulate

N, W = map(int, input().split())
items = []
for i in range(N):
    items.append(tuple(map(int, input().split())))

w_max = items[0][0] + 3
w0 = items[0][0]
w0_list = []
w1_list = []
w2_list = []
w3_list = []
for item in items:
    w, v = item
    if w == w0:
        w0_list.append(v)
    if w == w0 + 1:
        w1_list.append(v)
    if w == w0 + 2:
        w2_list.append(v)
    if w == w0 + 3:
        w3_list.append(v)
w0_list = sorted(w0_list, reverse=True)
w1_list = sorted(w1_list, reverse=True)
w2_list = sorted(w2_list, reverse=True)
w3_list = sorted(w3_list, reverse=True)

w0_accum = tuple(accumulate(w0_list))
w1_accum = tuple(accumulate(w1_list))
w2_accum = tuple(accumulate(w2_list))
w3_accum = tuple(accumulate(w3_list))

ans = 0
for i in range(len(w0_list)+1):
    for j in range(len(w1_list)+1):
        for k in range(len(w2_list)+1):
            for m in range(len(w3_list)+1):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * m > W:
                    continue
                else:
                    tmp = 0
                    if i > 0:
                        tmp += w0_accum[i-1]
                    if j > 0:
                        tmp += w1_accum[j-1]
                    if k > 0:
                        tmp += w2_accum[k-1]
                    if m > 0:
                        tmp += w3_accum[m-1]
                    ans = max(ans, tmp)
print(ans)

Solution (Python):
from itertools import accumulate
N,W = map(int,input().split())
V = [[] for _ in range(4)]
w0 = 0
for i in range(N):
    w,v = map(int,input().split())
    if i==0:
        V[0].append(v)
        w0 = w
    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)

Solution (Python):
from itertools import accumulate
N, W_limit = map(int, input().split())
W, V = [], []
for i in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)


base_W = W[0]

W = [w - base_W for w in W]


Items = [[] for i in range(4)]
for w, v in zip(W, V):
    Items[w].append(v)


Items = [[0] + sorted(x, reverse=True) for x in Items]
Items = [list(accumulate(x)) for x in Items]


ans = 0
for w0 in range(len(Items[0])):
    for w1 in range(len(Items[1])):
        for w2 in range(len(Items[2])):
            for w3 in range(len(Items[3])):
                tmp_W = (w0 * base_W) + (w1 * (base_W + 1)) + (w2 * (base_W + 2)) + (w3 * (base_W + 3))
                if tmp_W > W_limit:
                    continue
                tmp_V = Items[0][w0] + Items[1][w1] + Items[2][w2] + Items[3][w3]
                ans = max(ans, tmp_V)

print(ans)

Solution (Python):
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for weight, value in WV:
    dp_old = dp.copy()
    for k, v in dp_old.items():
        if k + weight <= W:
            dp[k + weight] = max(dp.get(k + weight, 0), v + value)
ans = 0
for k, v in dp.items():
    ans = max(ans, v)
print(ans)

Solution (Python):
N, W = map(int, input().split())
wlist = [0] * N
vlist = [0] * N
for i in range(N):
	wlist[i], vlist[i] = map(int, input().split())
minw = min(wlist)
w = list()
for i in range(4):
	w.append(list())
for i in range(N):
	w[wlist[i] - minw].append(vlist[i])
for i in range(4):
	w[i].sort(reverse = True)
ans = 0
sumw0 = 0
sumv0 = 0
for i in range(len(w[0]) + 1):
	sumw1 = 0
	sumv1 = 0
	for j in range(len(w[1]) + 1):
		sumw2 = 0
		sumv2 = 0
		for k in range(len(w[2]) + 1):
			sumw3 = 0
			sumv3 = 0
			for l in range(len(w[3]) + 1):
				sumw = sumw0 + sumw1 + sumw2 + sumw3
				sumv = sumv0 + sumv1 + sumv2 + sumv3
				if sumw <= W:
					ans = max(ans, sumv)
				if l != len(w[3]):
					sumw3 += minw + 3
					sumv3 += w[3][l]
			if k != len(w[2]):
				sumw2 += minw + 2
				sumv2 += w[2][k]
		if j != len(w[1]):
			sumw1 += minw + 1
			sumv1 += w[1][j]
	if i != len(w[0]):
		sumw0 += minw
		sumv0 += w[0][i]
print(ans)

Solution (Python):
from itertools import accumulate
N, W = map(int, input().split())
w0, w1, w2, w3 = [], [], [], []
base_w = -1
for i in range(N):
    w, v = map(int, input().split())
    if base_w < 0:
        base_w = w

    
    w -= base_w
    if w == 0:
        w0.append(v)
    elif w == 1:
        w1.append(v)
    elif w == 2:
        w2.append(v)
    else:
        w3.append(v)


w0.sort(reverse=True)
w1.sort(reverse=True)
w2.sort(reverse=True)
w3.sort(reverse=True)


w0 = [0] + list(accumulate(w0))
w1 = [0] + list(accumulate(w1))
w2 = [0] + list(accumulate(w2))
w3 = [0] + list(accumulate(w3))

ans = 0
for i0 in range(len(w0)):
    for i1 in range(len(w1)):
        for i2 in range(len(w2)):
            for i3 in range(len(w3)):
                if base_w * i0 + (base_w + 1) * i1 + (base_w + 2) * i2 + (base_w + 3) * i3 > W:
                    continue
                ans = max(ans, w0[i0] + w1[i1] + w2[i2] + w3[i3])

print(ans)

Solution (Python):

n, W = map(int, input().split())
s = []
for i in range(n):
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
s0 = []
s1 = []
s2 = []
s3 = []
for i in range(n):
    if i == 0:
        w0 = s[i][0]
        s0.append(s[i])
    elif s[i][0] == w0:
        s0.append(s[i])
    elif s[i][0] == w0 + 1:
        s1.append(s[i])
    elif s[i][0] == w0 + 2:
        s2.append(s[i])
    elif s[i][0] == w0 + 3:
        s3.append(s[i])
s0.sort(key=lambda x: x[1], reverse=True)
s1.sort(key=lambda x: x[1], reverse=True)
s2.sort(key=lambda x: x[1], reverse=True)
s3.sort(key=lambda x: x[1], reverse=True)
w = []
v = []
t0 = 0
t1 = 0
t2 = 0
t3 = 0
u0 = 0
u1 = 0
u2 = 0
u3 = 0
u = []
for h in range(-1, len(s0)):
    if h == -1:
        t0 = 0
        u0 = 0
    else:
        t0 += s0[h][0]
        u0 += s0[h][1]
    for i in range(-1, len(s1)):
        if i == -1:
            t1 = 0
            u1 = 0
        else:
            t1 += s1[i][0]
            u1 += s1[i][1]
        for j in range(-1, len(s2)):
            if j == -1:
                t2 = 0
                u2 = 0
            else:
                t2 += s2[j][0]
                u2 += s2[j][1]
            for k in range(-1, len(s3)):
                if k == -1:
                    t3 = 0
                    u3 = 0
                else:
                    t3 += s3[k][0]
                    u3 += s3[k][1]
                if t0 + t1 + t2 + t3 <= W:
                    u.append(u0 + u1 + u2 + u3)
print(max(u))

Solution (Python):
N,W=map(int,input().split())
List=[[] for i in range(4)]
for i in range(N):
  w,v=map(int,input().split())
  if i==0:
    List[0].append(v)
    w0=w
  else:
    List[w-w0].append(v)
ans=0
for i in range(4):
  List[i].sort(key=lambda x:-x)
n0,n1,n2,n3=len(List[0]),len(List[1]),len(List[2]),len(List[3])
for i in range(n0+1):
  for j in range(n1+1):
    for p in range(n2+1):
      for q in range(n3+1):
        if w0*i+(w0+1)*j+(w0+2)*p+(w0+3)*q<=W:
          ans=max(ans,sum(List[0][:i])+sum(List[1][:j])+sum(List[2][:p])+sum(List[3][:q]))
print(ans)

Solution (Python):
n,w=map(int,input().split())
d={}
p=0
for i in range(n):
    a,b=map(int,input().split())
    if a in d: d[a].append(b)
    else: d[a]=[b]
    p=max(p,a)

for i in range(4):
    if p-i in d:d[p-i].sort(reverse=True)
    else: d[p-i]=[0]

l={}
for i in d:
    t=0
    l[i]=[0]
    for j in d[i]:
        t+=j
        l[i].append(t)
ans=0
for ai,i in enumerate(l[p]):
    for bj,j in enumerate(l[p-1]):
        for ck,k in enumerate(l[p-2]):
            for em,m in enumerate(l[p-3]):
                x=ai*p+bj*(p-1)+ck*(p-2)+em*(p-3)
                if x<=w:
                    ans=max(ans,i+j+k+m)
print(ans)

Solution (Python):
n,w=map(int,input().split())
d={}
p=0
for i in range(n):
    a,b=map(int,input().split())
    if a in d: d[a].append(b)
    else: d[a]=[b]
    p=max(p,a)

for i in range(4):
    if p-i in d:d[p-i].sort(reverse=True)
    else: d[p-i]=[0]

l={}
for i in d:
    t=0
    l[i]=[0]
    for j in d[i]:
        t+=j
        l[i].append(t)
ans=0
for ai,i in enumerate(l[p]):
    for bj,j in enumerate(l[p-1]):
        for ck,k in enumerate(l[p-2]):
            for em,m in enumerate(l[p-3]):
                x=ai*p+bj*(p-1)+ck*(p-2)+em*(p-3)
                if x<=w:
                    ans=max(ans,i+j+k+m)
print(ans)

Solution (Python):
from collections import defaultdict
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w], v_cur+v)
print(max(dp.values()))

Solution (Python):
from itertools import accumulate
from collections import deque

N,W=list(map(int,input().split()))
arr=[deque([]) for i in range(4)]

w1,v=list(map(int,input().split()))
arr[0].append(v)

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

for i in range(4):
    arr[i]=sorted(arr[i],reverse=True)
    arr[i]=deque(accumulate(arr[i]))
    arr[i].appendleft(0)

ans=0
for i in range(len(arr[0])):
    for j in range(len(arr[1])):
        for k in range(len(arr[2])):
            for h in range(len(arr[3])):
                weight=(i+j+k+h)*w1+j+2*k+3*h
                value=arr[0][i]+arr[1][j]+arr[2][k]+arr[3][h]
                if weight>W:
                    break
                elif value>ans:
                    ans=value
print(ans)

Solution (Python):
N,W=map(int,input().split())
data_list=[]
for j in range(N):
    w,v=map(int,input().split())
    data_list.append((w,v))
from collections import defaultdict
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()))

Solution (Python):

n,w=map(int,input().split())
v=[[] for i in range(4)]
w1,v1=map(int,input().split())
v[0].append(v1)
for i in range(1,n):
    tw,tv=map(int,input().split())
    v[tw-w1].append(tv)
for i in range(4):
    v[i].sort(reverse=True)
cum=[[0] for i in range(4)]
for i in range(4):
    for j in range(len(v[i])):
        cum[i].append(cum[i][j]+v[i][j])
s=0
for i in range(len(v[0])+1):
    for j in range(len(v[1])+1):
        for k in range(len(v[2])+1):
            for l in range(len(v[3])+1):
                if w1*(i+j+k+l)+j+2*k+3*l>w:
                    continue
                s=max(s,cum[0][i]+cum[1][j]+cum[2][k]+cum[3][l])
print(s)

Solution (Python):
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w_adjust = []
for i in range(N):
    w_adjust.append(w[i]-w[0])

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

for i in range(N):
    for j in range(3*N):
        for k in range(N):
            if j + w_adjust[i] > W - a*(k+1):
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            else:
                dp[i+1][j+w_adjust[i]][k+1] = max(dp[i+1][j+w_adjust[i]][k+1], dp[i][j][k] + v[i])
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
ans = [0]
for i in range(1, N+1):
    if W - a*i >= 0 and W - a*i < N*3 + 3:
        ans.append(dp[N][W-a*i][i])

if W - a*N > N*3:
    things = W//w[0]
    if things > N:
        ans.append(sum(v))

elif len(ans) == 1:
    things = W//w[0]
    v.sort()
    v.reverse()
    ans_1 = 0
    for i in range(things):
        ans_1 += v[i]
    ans.append(ans_1)

print(max(ans))

Solution (Python):
N,W = map(int,input().split())
v = [[] for _ in range(4)]
w0,vv = map(int,input().split())
v[0].append(vv)
for _ in range(N-1):
    ww,vv = map(int,input().split())
    v[ww-w0].append(vv)
for i in range(4):
    v[i].sort(reverse=True)
cum =[[0] for _ in range(4)]
for i in range(4):
    for j in range(len(v[i])):
        cum[i].append(cum[i][j]+v[i][j])
ans = 0
for i in range(len(v[0])+1):
    for j in range(len(v[1])+1):
        for k in range(len(v[2])+1):
            for l in range(len(v[3])+1):
                if (i+j+k+l)*w0 + j + 2*k + 3*l > W:
                    continue
                
                candidate = cum[0][i] + cum[1][j] + cum[2][k] + cum[3][l]
                ans = max(ans,candidate)
print(ans)

Solution (Python):
N,W = map(int,input().split())
l0=[]
l1=[]
l2=[]
l3=[]
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    if w == w1:
        l0.append(v)
    elif w == w1+1:
        l1.append(v)
    elif w == w1+2:
        l2.append(v)
    elif w == w1+3:
        l3.append(v)

l0.sort()
l0.reverse()
l1.sort()
l1.reverse()
l2.sort()
l2.reverse()
l3.sort()
l3.reverse()
l0 = [0]+l0
l1 = [0]+l1
l2 = [0]+l2
l3 = [0]+l3
import numpy as np
l0 = np.cumsum(np.array(l0))
l1 = np.cumsum(np.array(l1))
l2 = np.cumsum(np.array(l2))
l3 = np.cumsum(np.array(l3))

ans = 0
for i in range(len(l0)):
    for j in range(len(l1)):
        for k in range(len(l2)):
            for l in range(len(l3)):
                if i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3)<=W:
                    if ans < l0[i]+l1[j]+l2[k]+l3[l]:
                         ans = l0[i]+l1[j]+l2[k]+l3[l]

print(ans)

Solution (Python):
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
x=[[] for _ in range(4)]
w0=wv[0][0]
for w,v in wv:
    x[w-w0].append(v)
for i in range(4):
    x[i].sort()
    x[i]=x[i][::-1]
y=[[0] for i in range(4)]
for i in range(4):
    if len(x[i])>0:
        y[i].append(x[i][0])
for i in range(4):
    for j in range(1,len(x[i])):
        y[i].append(y[i][-1]+x[i][j])
res=[]
for a in range(len(x[0])+1):
    for b in range(len(x[1])+1):
        for c in range(len(x[2])+1):
            for d in range(len(x[3])+1):
                if w0*a+(w0+1)*b+(w0+2)*c+(w0+3)*d<=W:
                    res.append(y[0][a]+y[1][b]+\
                              y[2][c]+y[3][d])
print(max(res))

Solution (Python):
from collections import defaultdict
N, W = map(int, input().split())
data_list = []
for _ 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()))

Solution (Python):

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())

memo = {}

def knapsack(i, j):
    key = '{}-{}'.format(i, j)
    if key in memo:
        return memo[key]
    if i == N:
        r = 0
    elif j < w[i]:
        r = knapsack(i + 1, j)
    else:
        r = max([knapsack(i + 1, j), knapsack(i + 1, j - w[i]) + v[i]])
    memo[key] = r
    return r

print(knapsack(0, W))

Solution (Python):
N, W = map(int, input().split())
app = [list(map(int, input().split())) for i in range(N)]

data = [[] for i in range(4)]

for w, v in app:
    if w == app[0][0]:
        data[0].append(v)
    elif w == app[0][0] + 1:
        data[1].append(v)
    elif w == app[0][0] + 2:
        data[2].append(v)
    elif w == app[0][0] + 3:
        data[3].append(v)

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

for i in range(4):
    for j in range(len(data[i])-1):
        data[i][j+1] += data[i][j]

for i in range(4):
    data[i].append(0)
    data[i].sort()

ans = 0
for a in range(len(data[0])):
    for b in range(len(data[1])):
        for c in range(len(data[2])):
            for d in range(len(data[3])):
                if a * app[0][0] + b * (app[0][0]+1) + c * (app[0][0]+2) + d * (app[0][0]+3) <= W:
                    ans = max(ans, data[0][a] + data[1][b] + data[2][c] + data[3][d])

print(ans)

Solution (Python):
N, W = map(int, input().split())
V0, V1, V2, V3 = [], [], [], []
w0 = 0
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        V0.append(v)
        w0 = w
    elif w0 == w:
        V0.append(v)
    elif w0 + 1 == w:
        V1.append(v)
    elif w0 + 2 == w:
        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)
vl0 = len(V0)
vl1 = len(V1)
vl2 = len(V2)
vl3 = len(V3)
V0_sum = [0] * (vl0 + 1)
V1_sum = [0] * (vl1 + 1)
V2_sum = [0] * (vl2 + 1)
V3_sum = [0] * (vl3 + 1)
for i in range(1, vl0 + 1):
    V0_sum[i] = V0_sum[i - 1] + V0[i - 1]
for i in range(1, vl1 + 1):
    V1_sum[i] = V1_sum[i - 1] + V1[i - 1]
for i in range(1, vl2 + 1):
    V2_sum[i] = V2_sum[i - 1] + V2[i - 1]
for i in range(1, vl3 + 1):
    V3_sum[i] = V3_sum[i - 1] + V3[i - 1]
w1, w2, w3 = w0 + 1, w0 + 2, w0 + 3
num = 0

for v0 in range(vl0 + 1):
    for v1 in range(vl1 + 1):
        for v2 in range(vl2 + 1):
            for v3 in range(vl3 + 1):
                w = v0 * w0 + v1 * w1 + v2 * w2 + v3 * w3
                if w <= W:
                    q = V0_sum[v0] + V1_sum[v1] + V2_sum[v2] + V3_sum[v3]
                    num = max(num, q)

print(num)

Solution (Python):

N, W = map(int,input().split())
L = [list(map(int,input().split())) for k in range(N)]

wmin = L[0][0]
M = [[],[],[],[]]
for load in L:
    M[load[0]-wmin].append(load[1])

M0 = sorted(M[0])[::-1]
M1 = sorted(M[1])[::-1]
M2 = sorted(M[2])[::-1]
M3 = sorted(M[3])[::-1]

ans = 0
for p in range(len(M0)+1):
    for q in range(len(M1)+1):
        for r in range(len(M2)+1):
            for s in range(len(M3)+1):
                weight = p*wmin + q*(wmin+1) + r*(wmin+2) + s*(wmin+3)
                if weight <= W:
                    ans = max(ans,sum(M0[:p])+sum(M1[:q])+sum(M2[:r])+sum(M3[:s]))
print(ans)

Solution (Python):
N, W = map(int, input().split())
w0, v0 = map(int, input().split())
W0 = [0, v0]
W1, W2, W3 = [0], [0], [0]
for i in range(N-1):
    w, v = map(int, input().split())
    if w == w0:
        W0.append(v)
    elif w == w0 + 1:
        W1.append(v)
    elif w == w0 + 2:
        W2.append(v)
    else:
        W3.append(v)
W0.sort()
W1.sort()
W2.sort()
W3.sort()
for i in range(1, len(W0)):
    W0[i] += W0[i-1]
for i in range(1, len(W1)):
    W1[i] += W1[i-1]
for i in range(1, len(W2)):
    W2[i] += W2[i-1]
for i in range(1, len(W3)):
    W3[i] += W3[i-1]

MaxValue = 0
for i in range(len(W0)):
    for j in range(len(W1)):
        for k in range(len(W2)):
            for l in range(len(W3)):
                if w0*i + (w0+1)*j + (w0+2)*k + (w0+3)*l <= W:
                    Total = (W0[-1]-W0[-1-i]) + (W1[-1]-W1[-1-j]) + (W2[-1]-W2[-1-k]) + (W3[-1]-W3[-1-l])
                    MaxValue = max(MaxValue, Total)
print(MaxValue)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,w = li()
wv = []
for _ in range(n):
    wv.append(tuple(li()))
    
w0 = wv[0][0]
dic = {w0+i: [] for i in range(4)}
for k,v in wv:
    dic[k].append(v)
    
for wi in range(w0,w0+4):
    dic[wi] = [0] + sorted(dic[wi], reverse=True)
    dic[wi] = list(accumulate(dic[wi]))
    
ans = 0
for idx1, w1 in enumerate(dic[w0]):
    
    for idx2, w2 in enumerate(dic[w0+1]):
        
        for idx3, w3 in enumerate(dic[w0+2]):
            
            for idx4, w4 in enumerate(dic[w0+3]):
                
                if w0*idx1 + (w0+1)*idx2 + (w0+2)*idx3 + (w0+3)*idx4 > w:
                    continue
                
                ans = max(ans, w1+w2+w3+w4)
        
print(ans)

Solution (Python):
from itertools import accumulate
N, W = map( int, input().split())
o, k = map( int, input().split())
A = [k]
B, C, D = [], [], []
for _ in range(N-1):
    w, v = map( int, input().split())
    if w == o:
        A.append(v)
    elif w == o+1:
        B.append(v)
    elif w == o+2:
        C.append(v)
    else:
        D.append(v)
A.sort(key=None, reverse = True)
B.sort(key=None, reverse = True)
C.sort(key=None, reverse = True)
D.sort(key=None, reverse = True)
A = [0] + list(accumulate(A))
B = [0] + list(accumulate(B))
C = [0] + list(accumulate(C))
D = [0] + list(accumulate(D))




ans = 0
for i in range( len(A)):
    for j in range( len(B)):
        for k in range( len(C)):
            for l in range( len(D)):
                if i*o + j*(o+1) + k*(o+2) + l*(o+3) <= W:

                    ans = max( ans, A[i]+B[j]+C[k]+D[l])
print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def dfs(i, ws, d, W):
    if i >= len(ws):
        return 0
    w = ws[i]

    ans = dfs(i + 1, ws, d, W)
    total = 0
    for j in range(len(d[w])):
        total += d[w][j]
        if (j + 1) * w <= W:
            ans = max(ans, dfs(i + 1, ws, d, W - (j + 1) * w) + total)
    return ans


def main():
    N, W = map(int, input().split())

    d = defaultdict(list)
    for _ in range(N):
        w, v = map(int, input().split())
        d[w].append(v)
    for w in d.keys():
        d[w].sort(reverse=True)

    print(dfs(0, list(d.keys()), d, W))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,w = li()
wi,vi = li()
w0 = wi
v_list = [[] for _ in range(4)]
v_list[0].append(vi)

for _ in range(n-1):
    wi,vi = li()
    v_list[wi-w0].append(vi)
    
for i in range(4):
    v_list[i].sort(reverse=True)
    v_list[i] = list(accumulate([0] + v_list[i]))
    
ans = 0
res = w
for w1 in range(len(v_list[0])):
    
    if w - w0*(w1) < 0:
        pass
    else:
        res1 = w - w0*(w1)
        ans1 = v_list[0][w1]
        ans = max(ans, ans1)
    

    for w2 in range(len(v_list[1])):

        if res1 - (w0+1)*(w2) < 0:
            pass
        
        else:
            res2 = res1 - (w0+1)*(w2)
            ans2 = ans1 + v_list[1][w2]
            ans = max(ans, ans2)

        
        
        for w3 in range(len(v_list[2])):
            
            if res2 - (w0+2)*(w3) < 0:
                pass
            
            else:
                res3 = res2 - (w0+2)*(w3)
                ans3 = ans2 + v_list[2][w3]
                ans = max(ans, ans3)
                
            
            for w4 in range(len(v_list[3])):

                if res3 - (w0+3)*(w4) < 0:
                    pass
                
                else:
                    res4 = res3 - (w0+3)*(w4)
                    ans4 = ans3 + v_list[3][w4]
                    ans = max(ans, ans4)

                
print(ans)

Solution (Python):
from collections import defaultdict
from copy import copy
N,W = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

dp = defaultdict(lambda: 0)
dp[0] = 0
for w,v in src:
    dp2 = copy(dp)
    for pw,pv in dp.items():
        if pw+w > W: continue
        defv = dp[pw+w] if pw+w in dp else 0
        dp2[pw+w] = max(defv, pv+v)
    dp = dp2
print(max(dp.values()))

Solution (Python):
import sys
from itertools import accumulate as acc

def main():
    N, W = map(int, input().split())
    V = [[] for _ in '1234']

    w, v = map(int, input().split())
    w0 = w
    V[0].append(v)
    for e in sys.stdin:
        w, v = map(int, e.split())
        V[w - w0].append(v)

    for i in range(4):
        V[i] = [0] + list(acc(sorted(V[i], reverse=True)))

    ans = 0
    a, b, c, d = map(len, V)
    for i in range(a):
        wi = w0 * i
        if wi > W:
            break
        vi = V[0][i]
        for j in range(b):
            wj = wi + (w0 + 1) * j
            if wj > W:
                break
            vj = vi + V[1][j]
            for k in range(c):
                wk = wj + (w0 + 2) * k
                if wk > W:
                    break
                vk = vj + V[2][k]

                l = min((W - wk) // (w0 + 3), d - 1)
                v = vk + V[3][l]
                ans = max(ans, v)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
V = [[] for i in range(4)]
w0, v0 = map(int, input().split())
V[0].append(v0)
for i in range(N - 1):
  w, v = map(int, input().split())
  V[w - w0].append(v)
V = [[0] + sorted(V[i], reverse=True) for i in range(4)]
value = 0
val = [0] * 4
for i in range(min(W // w0 + 1, len(V[0]))):
  val[0] += V[0][i]
  for j in range(min((W - w0 * i) // (w0 + 1) + 1, len(V[1]))):
    val[0] += V[1][j]
    val[1] += V[1][j]
    for k in range(min((W - w0 * (i + j) - j) // (w0 + 2) + 1, len(V[2]))):
      val[0] += V[2][k]
      val[2] += V[2][k]
      for l in range(min((W - w0 * (i + j + k) - j - k * 2) // (w0 + 3) + 1, len(V[3]))):
        val[0] += V[3][l]
        val[3] += V[3][l]
      value = max(value, val[0])
      val[0] -= val[3]
      val[3] = 0
    val[0] -= val[2]
    val[2] = 0
  val[0] -= val[1]
  val[1] = 0
print(value)

Solution (Python):
n,w = map(int,input().split())
w1,v1 = map(int,input().split())
if n == 1:
    if w1 <= w:
        print(v1)
    else:
        print(0)
else:
    a = [v1] 
    b = []
    c = []
    d = []
    for i in range(n-1):
        p,q = map(int,input().split())
        if p == w1:
            a.append(q)
        elif p == w1 + 1:
            b.append(q)
        elif p == w1 + 2:
            c.append(q)
        else:
            d.append(q)
    a.sort()
    b.sort()
    c.sort()
    d.sort()
    a = a[::-1]
    b = b[::-1]
    c = c[::-1]
    d = d[::-1]
    
    jkl = 0
    ass = 0
    for i in range(len(a)+1):
        for j in range(len(b)+1):
            for h in range(len(c)+1):
                for g in range(len(d)+1):
                    if w1*(i+j+h+g)+j+2*h+3*g <= w:
                        ans = sum(a[:i:]) + sum(b[:j:]) + sum(c[:h:]) + sum(d[:g:])
                        ass = max(ass,ans)
    print(ass)

Solution (Python):
from collections import defaultdict as dd
from itertools import accumulate as ac
from itertools import product as pr

N,W=map(int,input().split())
d=dd(list)
for _ in range(N):
  w,v=map(int,input().split())
  d[w].extend([v])
d=dict(d)
for i in d.keys():
  d[i].sort(reverse=True)
  d[i]=[0]+list(ac(d[i]))

l=[]
key=list(d.keys())
for val in pr(*map(enumerate,d.values())):
  weight=sum(map(lambda x,y:x*y[0],key,val))
  value=sum(map(lambda x:x[1],val))
  if weight<=W:
    l.extend([value])

print(max(l))