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):
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w0 = WV[0][0]
    WV[0][0] = 0
    V = {i: [] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    S = [[0] for i in range(4)]
    for i in range(4):
        for b in V[i]:
            S[i].append(S[i][-1] + b)
    ans = 0
    for i, v0 in enumerate(S[0]):
        for j, v1 in enumerate(S[1]):
            for k, v2 in enumerate(S[2]):
                for m, v3 in enumerate(S[3]):
                    w_cur = w0*(i+j+k+m) + j + 2*k + 3*m
                    if W < w_cur:
                        continue
                    ans = max(ans, v0+v1+v2+v3)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

N, W = map(int, input().split())
d = {i: [] for i in range(4)}
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    w -= w0
    d[w].append(v)

wv = [[] for _ in range(4)]
for k, v in d.items():
    v.sort(reverse=True)
    v = [0] + v
    wv[k] = tuple(accumulate(v))



ans = 0
for c0, v0 in enumerate(wv[0]):
    for c1, v1 in enumerate(wv[1]):
        for c2, v2 in enumerate(wv[2]):
            for c3, v3 in enumerate(wv[3]):
                weight = w0 * (c0 + c1 + c2 + c3) + c1 + c2 * 2 + c3 * 3
                val = v0 + v1 + v2 + v3
                if weight > W:
                    continue
                ans = max(ans, val)

print(ans)

Solution (Python):
N,W = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

w = L[0][0]
M = 0
for i in range(N):
    M += L[i][0]-w
dp = [[[0]*(M+1) for _ in range(N+1)] for _ in range(N+1)]
t = 0
for i in range(N):
    t += L[i][0]-w
    for j in range(i+2):
        for k in range(t+1):
            if j*w+k < L[i][0]:
                dp[i+1][j][k] = dp[i][j][k]
            else:
                dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-(L[i][0]-w)]+L[i][1])

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

Solution (Python):
N,W = map(int,input().split())
WV = [tuple(map(int,input().split())) for i in range(N)]
w0 = WV[0][0]
a = [[],[],[],[]]
for w,v in WV:
    i = w-w0
    a[i].append(v)
for i in range(4):
    a[i].sort(reverse=True)
c = [[0] for _ in range(4)]
for i in range(4):
    for b in a[i]:
        c[i].append(c[i][-1] + b)

ans = 0
for i,v0 in enumerate(c[0]):
    for j,v1 in enumerate(c[1]):
        for k,v2 in enumerate(c[2]):
            for l,v3 in enumerate(c[3]):
                w = w0*(i+j+k+l) + j + k*2 + l*3
                if w>W: break
                ans = max(ans, v0+v1+v2+v3)
print(ans)

Solution (Python):
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
w1 = wv[0][0]
l1, l2, l3, l4 = [], [], [], []

for wi, vi in wv:
    if wi==w1:
        l1.append(vi)
    elif wi==w1+1:
        l2.append(vi)
    elif wi==w1+2:
        l3.append(vi)
    else:
        l4.append(vi)

l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)

l1_acc = [0]
l2_acc = [0]
l3_acc = [0]
l4_acc = [0]

for l1_i in l1:
    l1_acc.append(l1_acc[-1]+l1_i)

for l2_i in l2:
    l2_acc.append(l2_acc[-1]+l2_i)

for l3_i in l3:
    l3_acc.append(l3_acc[-1]+l3_i)

for l4_i in l4:
    l4_acc.append(l4_acc[-1]+l4_i)

ans = 0

for i in range(len(l1)+1):
    for j in range(len(l2)+1):
        for k in range(len(l3)+1):
            for l in range(len(l4)+1):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    ans = max(ans, l1_acc[i]+l2_acc[j]+l3_acc[k]+l4_acc[l])
    
print(ans)

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

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

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from bisect import bisect_right

N,W = LI()
w,v = LIR(N,2)

w_list = []
for i in range(N+1):
    for j in range(i*w[0],i*(w[0]+3)+1):
        w_list.append(j)
w_list = sorted(list(set(w_list)))
M = len(w_list)

d = {}
temp = 0
for wl in w_list:
    d[temp] = wl
    temp += 1

dp = [[0]*M for _ in range(N)]
for i in range(N):
    for j in range(M):
        dp[i][j] = dp[i-1][j]
        x = d[j]-w[i]
        if x >= 0:
            p = bisect_right(w_list,x)
            dp[i][j] = max(dp[i][j], dp[i-1][p-1]+v[i])

p = bisect_right(w_list,W)
print(dp[N-1][p-1])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

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

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

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

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

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

dfs(cnt0)

print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7
from collections import defaultdict

def ddprint(x):
  if DBG:
    print(x)

n,ww = inm()
w = []
v = []
for i in range(n):
    www,vvv = inm()
    w.append(www)
    v.append(vvv)
h = [ defaultdict(int) for i in range(n+1) ]
for i in range(n):
    h[i][0] = 0
for i in range(n):
    for u in h[i]:
        h[i+1][u] = max(h[i+1][u], h[i][u])
        if u+w[i] <= ww:
            h[i+1][u+w[i]] = max(h[i+1][u+w[i]], h[i][u]+v[i])
print(max(list(h[n].values())))

Solution (Python):
from itertools import accumulate

N, constW = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
L = [[] for _ in range(4)]
for w, v in WV:
  w -= W0
  L[w].append(v)
L[0].sort(reverse=True)
L0 = [0] + list(accumulate(L[0]))
l0 = len(L0) - 1
L[1].sort(reverse=True)
L1 = [0] + list(accumulate(L[1]))
l1 = len(L1) - 1
L[2].sort(reverse=True)
L2 = [0] + list(accumulate(L[2]))
l2 = len(L2) - 1
L[3].sort(reverse=True)
L3 = [0] + list(accumulate(L[3]))
l3 = len(L3) - 1
ans = 0
for i in range(1, constW//W0 + 1):
  rest = constW - i*W0
  for j in range(min(rest//3, i, l3) + 1):
    rest1 = rest - 3*j
    for k in range(min(rest1//2, i-j, l2) + 1):
      rest2 = rest1 - 2*k
      for l in range(min(rest2, i-j-k, l1) + 1):
        temp = L3[j] + L2[k] + L1[l] + L0[min(l0, i-j-k-l)]
        ans = max(ans, temp)
print(ans)

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

def main():
  N, constW = map(int, input().split())
  WV = [list(map(int, input().split())) for _ in range(N)]
  W0 = WV[0][0]
  L = [[] for _ in range(4)]
  for w, v in WV:
    w -= W0
    L[w].append(v)
  L[0].sort(reverse=True)
  L[1].sort(reverse=True)
  L[2].sort(reverse=True)
  L[3].sort(reverse=True)
  ans = 0
  for i in range(1, constW//W0 + 1):
    rest = constW - i*W0
    for j in range(min(rest//3, i) + 1):
      rest1 = rest - 3*j
      for k in range(min(rest1//2, i-j) + 1):
        rest2 = rest1 - 2*k
        for l in range(min(rest2, i-j-k) + 1):
          temp = sum(L[3][:j]) + sum(L[2][:k]) + sum(L[1][:l]) + sum(L[0][:i-j-k-l])
          ans = max(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
N, constW = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
L = [[] for _ in range(4)]
for w, v in WV:
  w -= W0
  L[w].append(v)
L[0].sort(reverse=True)
L[1].sort(reverse=True)
L[2].sort(reverse=True)
L[3].sort(reverse=True)
ans = 0
for i in range(1, constW//W0 + 1):
  rest = constW - i*W0
  for j in range(min(rest//3, i) + 1):
    rest1 = rest - 3*j
    for k in range(min(rest1//2, i-j) + 1):
      rest2 = rest1 - 2*k
      for l in range(min(rest2, i-j-k) + 1):
        temp = sum(L[3][:j]) + sum(L[2][:k]) + sum(L[1][:l]) + sum(L[0][:i-j-k-l])
        ans = max(ans, temp)
print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, W = lr()
WV = [lr() for _ in range(N)]

base = WV[0][0]
W0 = [0] + sorted([v for w, v in WV if w == base + 0], reverse=True)
W1 = [0] + sorted([v for w, v in WV if w == base + 1], reverse=True)
W2 = [0] + sorted([v for w, v in WV if w == base + 2], reverse=True)
W3 = [0] + sorted([v for w, v in WV if w == base + 3], reverse=True)
W0cum = np.array(W0).cumsum()
W1cum = np.array(W1).cumsum()
W2cum = np.array(W2).cumsum()
W3cum = np.array(W3).cumsum()
answer = 0
for a in range(len(W0)):
    for b in range(len(W1)):
        for c in range(len(W2)):
            for d in range(len(W3)):
                remain = W - a * base - b * (base+1) - c * (base+2) - d * (base+3)
                if remain < 0:
                    continue
                answer = max(answer, W0cum[a] + W1cum[b] + W2cum[c] + W3cum[d])

print(answer)

Solution (Python):
n,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(n)]
from collections import defaultdict
dp=defaultdict(int)
dp[0]=0
for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w<=W:
      dp[tw+w]=max(tv+v,dp[tw+w])
print(max(dp.values()))

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

Solution (Python):
N,W = map(int,input().split())
dic = {"0":[],"1":[],"2":[],"3":[]}
for i in range(N):
  w,v = map(int,input().split())
  if i == 0:
    Min = w
  if w == Min:
    dic["0"].append(v)
  elif w == Min+1:
    dic["1"].append(v)
  elif w == Min+2:
    dic["2"].append(v)
  elif w == Min+3:
    dic["3"].append(v)
    
dic["0"].sort(reverse=True)
dic["1"].sort(reverse=True)
dic["2"].sort(reverse=True)
dic["3"].sort(reverse=True)

ans = 0
for i in range(len(dic["0"])+1):
  for j in range(len(dic["1"])+1):
    for k in range(len(dic["2"])+1):
      for l in range(len(dic["3"])+1): 
        a = int(sum(dic["0"][:i])+sum(dic["1"][:j])+sum(dic["2"][:k])+sum(dic["3"][:l])) 
        b = int(i*Min+j*(Min+1)+k*(Min+2)+l*(Min+3))
        if a > ans and b <= W:
          ans = a
print(int(ans))

Solution (Python):
N,W = map(int,input().split())
from collections import defaultdict
wvl = defaultdict(list)
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        f_w = w
    wvl[w].append(v)

import itertools
for i in range(f_w, f_w+4):
    wvl[i] = [0] + list(itertools.accumulate(sorted(wvl[i], reverse=True)))

ans = 0
for i in range(101):
    if len(wvl[f_w])-1 < i:
        break
    for j in range(101-i):
        if len(wvl[f_w+1])-1 < j:
            break
        for k in range(101-i-j):
            if len(wvl[f_w+2])-1 < k:
                break
            rest = W - f_w * i - (f_w+1) * j - (f_w+2) * k
            l = min(rest // (f_w + 3), len(wvl[f_w+3])-1)
            if l < 0:
                break
            
            ans = max(ans, wvl[f_w][i] + wvl[f_w+1][j] + wvl[f_w+2][k] + wvl[f_w+3][l])
            
print(ans)

Solution (Python):
N, W = map(int, input().split())
D = {0: 0}
for i in range(N):
  w, v = map(int, input().split())
  A = [[i, D[i]] for i in D]
  for j in A:
    if j[0] + w <= W:
      if j[0] + w in D:
        D[j[0] + w] = max(D[j[0] + w], j[1] + v)
      else:
        D[j[0]+w] = j[1]+v
print(max(D[i] for i in D))

Solution (Python):
from itertools import accumulate
N, W = map(int, input().split())
xs = [[0] for _ in range(4)]
for i in range(1, N+1):
    w, v = map(int, input().split())
    if i == 1:
        cc = w
    xs[w-cc].append(v)
A, B, C, D = map(len, xs)
As, Bs, Cs, Ds = map(lambda x: list(accumulate([0]+sorted(x)[::-1])), xs)

def f(a, b, c, d):
    return As[a] + Bs[b] + Cs[c] + Ds[d]

def main():
    r = 0
    for a in range(A):
        for b in range(B):
            for c in range(C):
                for d in range(D):
                    w = cc*(a+b+c+d)+b+c*2+d*3
                    if w > W:
                        break
                    r = max(f(a,b,c,d), r)
    print(r)

main()

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

N, W = map(int, input().split())
A = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0: w0 = w
    A[w-w0].append(v)

B = [[0] for _ in range(4)]
for i in range(4):
    A[i].sort(reverse=True)
    b = 0
    for a in A[i]:
        b += a
        B[i].append(b)

ans = 0
for n1, b1 in enumerate(B[0]):
    for n2, b2 in enumerate(B[1]):
        for n3, b3 in enumerate(B[2]):
            n4 = min((W - n1*w0 - n2*(w0+1) - n3*(w0+2)) // (w0+3), len(B[3])-1)
            if n4 < 0: continue
            ans = max(ans, b1+b2+b3+B[3][n4])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
b = []
for _ in range(N):
  w, v = map(int, input().split())
  b.append((w, v))
wbias = b[0][0]
dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(N):
  for k in range(N):
    for j in range(3 * N + 1):
      if i + 1 <= N:
        dp[i + 1][k][j] = max(dp[i + 1][k][j], dp[i][k][j])
        if j + b[i][0] - wbias <= 3 * N and (k < N):
          dp[i + 1][k + 1][j + b[i][0] - wbias] = max(dp[i + 1][k + 1][j + b[i][0] - wbias], dp[i][k][j] + b[i][1])


res = 0
for k in range(N + 1):
  for j in range(3 * N + 1):
    if j + k * wbias <= W:
      res = max(res, dp[-1][k][j])
print(res)

Solution (Python):
N, W = map(int, input().split())
items = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        items[0].append(v)
    else:
        items[w-w0].append(v)

items = [[0]+sorted(items[i], reverse=True) for i in range(4)]
for i in range(4):
    for j in range(1, len(items[i])):
        items[i][j] += items[i][j-1]

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

print(ans)

Solution (Python):
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = map(int, input().split())
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = map(int, input().split())
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(len(e[0]) + 1):
        for b in range(len(e[1]) + 1):
            for c in range(len(e[2]) + 1):
                diff = W - (w1 * a + (w1 + 1) * b + (w1 + 2) * c)
                if diff < 0:
                    break
                d = min(len(e[3]), diff // (w1 + 3))
                ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print(solve())

Solution (Python):
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = map(int, input().split())
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = map(int, input().split())
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(min(len(e[0]), N) + 1):
        for b in range(min(len(e[1]), N - a) + 1):
            for c in range(min(len(e[2]), N - a - b) + 1):
                diff = W - (w1 * a + (w1 + 1) * b + (w1 + 2) * c)
                if diff < 0:
                    break
                d = min(len(e[3]), diff // (w1 + 3))
                ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print(solve())

Solution (Python):
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = map(int, input().split())
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = map(int, input().split())
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(min(len(e[0]), N) + 1):
        for b in range(min(len(e[1]), N - a) + 1):
            for c in range(min(len(e[2]), N - a - b) + 1):
                for d in range(min(len(e[3]), N - a - b - c) + 1):
                    if w1 * a + (w1 + 1) * b + (w1 + 2) * c + (w1 + 3) * d > W:
                        break
                    ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print(solve())

Solution (Python):
import bisect
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]

Wlist=[0]+[j*w1+i for j in range(1,N+1) for i in range(3*j+1)]
Wlist=sorted(set(Wlist))
LW=len(Wlist)
dp=[[0]*LW for _ in range(N+1)]


for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(LW):
    if w<=Wlist[j]:      
      ind=bisect.bisect_right(Wlist,Wlist[j]-w)-1
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=bisect.bisect_right(Wlist,W)-1
print(dp[N][ind])

Solution (Python):
from collections import defaultdict
from itertools import product, accumulate

N, W = map(int, input().split())
items = defaultdict(list)
for _ in range(N):
    w, v = map(int, input().split())
    items[w].append(v)
weights = list(items.keys())
nums = {w: len(items[w]) for w in weights}
cumsum = {w: None for w in weights}
for i, w in enumerate(weights):
    items[w].sort(reverse=True)
    cumsum[w] = [0] + list(accumulate(items[w]))
ans = 0
for tup in product(*[range(nums[w] + 1) for w in weights]):
    temp_weight = sum(w * t for w, t in zip(weights, tup))
    if temp_weight > W: continue
    temp_value = sum(cumsum[w][t] for w, t in zip(weights, tup))
    ans = max(temp_value, ans)
print(ans)

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

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


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

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


print(max(ans_list))

Solution (Python):

import sys
input = sys.stdin.buffer.readline

INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N, W = getlist()
	stock = []
	for i in range(N):
		w, v = getlist()
		stock.append([w, v])
	w1 = stock[0][0]
	for i in range(N):
		stock[i][0] -= w1

	DP = [[[-INF] * (N + 1) for i in range(3 * N + 1)] for j in range(N + 1)]
	DP[0][0][0] = 0
	
	for i in range(N):
		for j in range(3 * N):
			for k in range(N):
				if DP[i][j][k] != -INF:
					DP[i + 1][j + stock[i][0]][k + 1] = max(DP[i + 1][j + stock[i][0]][k + 1], DP[i][j][k] + stock[i][1])
					DP[i + 1][j][k] = max(DP[i + 1][j][k], DP[i][j][k])

	
	ans = 0
	for i in range(3 * N + 1):
		for j in range(N + 1):
			if DP[N][i][j] != INF and i + j * w1 <= W:
				ans = max(ans, DP[N][i][j])
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
from collections import defaultdict

def main():
    N, W = map(int, input().split())
    d = defaultdict(list)
    w1 = 0
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0:
            w1 = w
        d[w].append(v)

    ans = 0
    d[w1].sort(reverse=True)
    d[w1 + 1].sort(reverse=True)
    d[w1 + 2].sort(reverse=True)
    d[w1 + 3].sort(reverse=True)

    for i in range(len(d[w1])+1):
        for j in range(len(d[w1+1])+1):
            for k in range(len(d[w1+2])+1):
                for l in range(len(d[w1+3])+1):
                    tmp = sum(d[w1][:i]) + sum(d[w1+1][:j]) + sum(d[w1+2][:k]) + sum(d[w1+3][:l])

                    if w1 * i + (w1+1) * j + (w1+2) * k + (w1+3) * l <= W:
                        ans = max(ans,tmp)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

n, wmax = map(int, input().split())
dp = [defaultdict(int) for _ in range(2)]
dp[0][0] = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    dp[(i+1)%2] = defaultdict(int)
    for j in range(n+1):
        for k in range(300):
            weight = j*w0+k
            if weight <= wmax:
                if weight - w >= 0:
                    dp[(i+1)%2][weight] = max(dp[(i+1)%2][weight], dp[i%2][weight - w] + v)
                dp[(i+1)%2][weight] = max(dp[(i+1)%2][weight], dp[i%2][weight])

print(max(list(dp[n%2].values())))

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

items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append((v, w))

w0 = items[0][1]
itemGrp = [[] for _ in range(4)]
for v, w in items:
    itemGrp[w - w0].append(v)

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

accItemGrp = []
for i in range(4):
    item = itemGrp[i]
    accValue = [0] * (len(item) + 1)
    for i in range(1, len(item) + 1):
        accValue[i] = accValue[i - 1] + item[i - 1]
    accItemGrp.append(accValue)

ans = 0
for n0 in range(len(itemGrp[0]) + 1):
    for n1 in range(len(itemGrp[1]) + 1):
        for n2 in range(len(itemGrp[2]) + 1):
            for n3 in range(len(itemGrp[3]) + 1):
                weight = (n0 + n1 + n2 + n3) * w0 + n1 + 2 * n2 + 3 * n3
                if weight <= W:
                    value = 0
                    for i, n in enumerate([n0, n1, n2, n3]):
                        value += accItemGrp[i][n]
                    ans = max(ans, value)

print(ans)

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

items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append((v, w))

w0 = items[0][1]
itemGrp = [[] for _ in range(4)]
for v, w in items:
    itemGrp[w - w0].append(v)

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

accItemGrp = []
for i in range(4):
    item = itemGrp[i]
    accValue = [0] * (len(item) + 1)
    for i in range(1, len(item) + 1):
        accValue[i] = accValue[i - 1] + item[i - 1]
    accItemGrp.append(accValue)

ans = 0
for n0 in range(len(itemGrp[0]) + 1):
    for n1 in range(len(itemGrp[1]) + 1):
        for n2 in range(len(itemGrp[2]) + 1):
            for n3 in range(len(itemGrp[3]) + 1):
                weight = (n0 + n1 + n2 + n3) * w0 + n1 + 2 * n2 + 3 * n3
                if weight <= W:
                    value = 0
                    for i, n in enumerate([n0, n1, n2, n3]):
                        value += accItemGrp[i][n]
                    ans = max(ans, value)

print(ans)

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

wvs = [[] for i in range(4)]
w0 = WV[0][0]
for w,v in WV:
    wvs[w-w0].append(v)

cumwvs = []
for vs in wvs:
    cums = [0]
    for v in sorted(vs, reverse=True):
        cums.append(cums[-1] + v)
    cumwvs.append(cums)

ans = 0
for i,a in enumerate(cumwvs[0]):
    if i*w0 > W: break
    for j,b in enumerate(cumwvs[1]):
        if i*w0 + j*(w0+1) > W: break
        for k,c in enumerate(cumwvs[2]):
            if i*w0 + j*(w0+1) + k*(w0+2) > W: break
            for l,d in enumerate(cumwvs[3]):
                if i*w0 + j*(w0+1) + k*(w0+2) + l*(w0+3) > W: break
                ans = max(ans, a+b+c+d)
print(ans)

Solution (Python):
n, W = map(int, input().split())
dp = [[[0] * 301 for _ in range(n + 1)] for _ in range(n + 1)]
li = [list(map(int, input().split())) for _ in range(n)]
p = li[0][0]
for i, x in enumerate(li):
    w, v = x
    w -= p
    for j in range(i + 1):
        for k in range(301):
            if k >= w:
                if dp[i][j][k - w] + v > dp[i][j + 1][k]:
                    dp[i + 1][j + 1][k] = dp[i][j][k - w] + v
                else:
                    dp[i + 1][j + 1][k] = dp[i][j + 1][k]
            else:
                dp[i + 1][j + 1][k] = dp[i][j + 1][k]
ans = 0
for i in range(n + 1):
    for k in range(301):
        if i * p + k <= W:
            ans = max(dp[n][i][k], ans)
print(ans)