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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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(ans)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7


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)

Solution (Python):

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)

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)

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):

def examD():
    N, W = LI()
    w = [0]*N
    v = [0]*N
    w[0], v[0] = LI()
    wbasic = w[0]
    for i in range(1,N):
        a, b = LI()
        w[i] = a-wbasic
        v[i] = b
    w[0] = 0
    dp =[[[0]*(3*N+1) for _ in range(N+1)]for _ in range(N+1)]
    for i in range(N):
        for j in range(N+1):
            for k in range(3*N+1):
                dp[i+1][j][k] = max(dp[i][j][k], dp[i+1][j][k])
                if w[i]<=k and j>=1:
                    if j*wbasic+k<=W:
                        dp[i+1][j][k] = max(dp[i][j-1][k-w[i]]+v[i], dp[i+1][j][k])
    ans = 0
    for v in dp[N]:
        ans = max(ans,max(v))

    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):

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

for i in range(4):
    sacklist[i].sort(reverse=True)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[]
sumlist2=[]
sumlist3=[]
sumlist4=[]
for _ in range(len1+1):
    sumlist1.append(sum(sacklist[0][:_]))
for _ in range(len2+1):
    sumlist2.append(sum(sacklist[1][:_]))
for _ in range(len3+1):
    sumlist3.append(sum(sacklist[2][:_]))
for _ in range(len4+1):
    sumlist4.append(sum(sacklist[3][:_]))
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
answer=0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if ((w1)*i+(w1+1)*j+(w1+2)*k+(w1+3)*m)<= W:
                    answer=max(answer,sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(answer)

Solution (Python):
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
data=[[] for i in range(4)]
w1=wv[0][0]
for u in wv:
    w,v=u
    data[w-w1].append(v)
for i in range(4):
    data[i].sort(reverse=True)
    data[i]=[0]+data[i]
    for j in range(1,len(data[i])):
        data[i][j]+=data[i][j-1]
a=len(data[0])
b=len(data[1])
c=len(data[2])
d=len(data[3])
ans=0
for i in range(a):
    for j in range(b):
        for k in range(c):
            for l in range(d):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    ans=max(ans,data[0][i]+data[1][j]+data[2][k]+data[3][l])
print(ans)

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

w = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
w[0].append(v1)
for _ in range(N - 1):
    a, b = map(int, input().split())
    w[a - w1].append(b)

for i in range(4):
    w[i].sort(reverse = True)
    for j in range(1, len(w[i])):
        w[i][j] += w[i][j - 1]


ans = 0
for a in range(len(w[0]) + 1):
    if a == 0:
        v_a = 0
    else:
        v_a = w[0][a - 1]
    for b in range(len(w[1]) + 1):
        if b == 0:
            v_b = 0
        else:
            v_b = w[1][b - 1]
        for c in range(len(w[2]) + 1):
            if c == 0:
                v_c = 0
            else:
                v_c = w[2][c - 1]
            cost = a * w1 + b * (w1 + 1) + c * (w1 + 2)
            if cost > W:
                pass
            else:
                lest = W - cost
                d = min(lest // (w1 + 3), len(w[3]))
                
                if d == 0:
                    v_d = 0
                else:
                    v_d = w[3][d - 1]

                ans = max(ans, v_a + v_b + v_c + v_d)

print (ans)

Solution (Python):
N,W=map(int,input().split())
w=[0]*N;v=[0]*N
for i in range(N):w[i],v[i]=map(int,input().split())
V=[[] for _ in [0]*4]
for i in range(N):V[w[i]-w[0]].append(v[i])
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(len(V[i])-1):V[i][j+1]+=V[i][j]
    V[i].insert(0,0)

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

Solution (Python):
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=sorted(list(dic.keys()),reverse=True)
  for key in tmp:
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
tmp=sorted(list(dic.keys()))
ans=0
for key in tmp:
  if key>l:
    break
  ans=max(ans,dic[key])
print(ans)

Solution (Python):
n,m=map(int,input().split())
w=[0]*n 
v=[0]*n
from collections import Counter
l=[]
for i in range(n):
    a,b=map(int,input().split())
    w[i]=a  
    v[i]=b 
a=min(w)
c=Counter(w)

cnt1=c[a]

v1=[v[i] for i in range(n) if w[i]==a]
v1.sort(reverse=1)
cnt2=c[a+1]
v2=[v[i] for i in range(n) if w[i]==a+1]
cnt3=c[a+2]
v3=[v[i] for i in range(n) if w[i]==a+2]
v2.sort(reverse=1)
v3.sort(reverse=1)
cnt4=c[a+3]
v4=[v[i] for i in range(n) if w[i]==a+3]
v4.sort(reverse=1)

pv1=[0]*(cnt1+1)
pv1[0]=0
for i in range(1,cnt1+1):
    pv1[i]=pv1[i-1]+v1[i-1]
pv2=[0]*(cnt2+1)  
pv2[0]=0
for i in range(1,cnt2+1):
    pv2[i]=pv2[i-1]+v2[i-1]
pv3=[0]*(cnt3+1) 
pv3[0]=0
for i in range(1,cnt3+1):
    pv3[i]=pv3[i-1]+v3[i-1]
ans=0 
pv4=[0]*(cnt4+1)
for i in range(1,cnt4+1):
    pv4[i]=pv4[i-1]+v4[i-1]
for i in range(0,cnt1+1):
    for j in range(0,cnt2+1):
        for k in range(0,cnt3+1):
            for z in range(0,cnt4+1):
                if (i)*a+(j)*(a+1)+(k)*(a+2)+z*(a+3)<=m:
                    ans=max(ans,pv1[i]+pv2[j]+pv3[k]+pv4[z])
print(ans)

Solution (Python):
n, w = map(int, input().split())
list_item = []
for _ in range(n):
  weight, value = map(int, input().split())
  list_item.append((weight, value))

dict_ks = {}
dict_ks[0] = 0
num_checked = 0
while num_checked < n:
  new_w, new_v = list_item[num_checked]
  for temp_w, temp_v in list(dict_ks.items()):
    if temp_w + new_w <= w:
      if temp_w + new_w not in dict_ks:
        dict_ks[temp_w + new_w] = temp_v + new_v
      else:
        dict_ks[temp_w + new_w] = max(dict_ks[temp_w + new_w], temp_v + new_v)
  num_checked += 1

print(max(dict_ks.values()))

Solution (Python):
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(int)
d[0]=0
for _ in range(n):
       w,u=map(int,input().split())
       for i,j in d.copy().items():
              if i+w<=m:d[i+w]=max(d[i+w],j+u)
print(max(d.values()))

Solution (Python):

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

dic = {}
dic[0] = 0

for i in range(N):

    odic = dic.copy()

    w,v = map(int,input().split())

    for j in odic:

        if j + w not in dic and j+w <= W:
            dic[j+w] = odic[j] + v

        elif j+w <= W:
            dic[j+w] = max(odic[j]+v,dic[j+w])

ans = 0

for i in dic:
    ans = max(ans,dic[i])

print (ans)

Solution (Python):
import collections

n, w = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n)]

dp = [collections.defaultdict(lambda: 0) for _ in range(n + 1)]
dp[0][0] = 0
for i, (w0, v0) in enumerate(ls):
    for w1, v1 in dp[i].items():
        if w1 <= w:
            dp[i + 1][w1] = max(dp[i + 1][w1], v1)
        if w0 + w1 <= w:
            if w0 + w1 in dp[i].keys():
                dp[i + 1][w0 + w1] = max(dp[i + 1][w0 + w1], dp[i][w0 + w1],
                                         v0 + v1)
            else:
                dp[i + 1][w0 + w1] = v0 + v1
print(max(dp[n].values()))

Solution (Python):
from itertools import accumulate
N, W = map(int, input().split())
Item = [[] for i in range(4)]
for i in range(N):
    wi, vi = map(int, input().split())
    if i == 0:
        Item[0].append(vi)
        w_base = wi
    else:
        Item[wi - w_base].append(vi)

w0, w1, w2, w3 = Item
w0 = [0] + list(accumulate(sorted(w0, reverse=True)))
w1 = [0] + list(accumulate(sorted(w1, reverse=True)))
w2 = [0] + list(accumulate(sorted(w2, reverse=True)))
w3 = [0] + list(accumulate(sorted(w3, reverse=True)))

ans = 0
for i in range(len(w0)):
    for j in range(len(w1)):
        for k in range(len(w2)):
            tmp_weight = w_base * i + (w_base + 1) * j + (w_base + 2) * k
            if tmp_weight > W:
                continue
            tmp_ans = w0[i] + w1[j] + w2[k] + w3[min((W - tmp_weight) // (w_base + 3), len(w3) - 1)]
            ans = max(ans, tmp_ans)

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, limit = LI()
weight = []
value = []
for w, v in LIR(n):
    weight += [w]
    value += [v]


w1 = min(weight)
w2, w3, w4 = w1 + 1, w1 + 2, w1 + 3
w1_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w1], reverse=True)))
w2_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w2], reverse=True)))
w3_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w3], reverse=True)))
w4_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w4], reverse=True)))


ans = 0
for i, j, k, l in product(range(len(w1_list)), range(len(w2_list)), range(len(w3_list)), range(len(w4_list) )):
    if i * w1 + j * w2 + k * w3 + l * w4 > limit:
        continue
    ans = max(ans, w1_list[i] + w2_list[j] + w3_list[k] + w4_list[l])



print(ans)

Solution (Python):

from itertools import accumulate as acc


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  
    for w, v in zip(*[iter(A)] * 2):  
        V[w - x].append(v)
    for i in range(4):  
        V[i] = tuple(acc([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

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

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

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    
    
    wv = sorted(list(dic.items()))
    tmp = [None for i in range(4)]
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] = [0] + l

    
    

    ans = 0
    for i in range(len(tmp[0])):
        for j in range(len(tmp[1])):
            for k in range(len(tmp[2])):
                for l in range(len(tmp[3])):
                    weight = base_w * i + (base_w + 1) * j + (base_w + 2) * k + (base_w + 3) * l
                    if weight <= W:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

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

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

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    wv = sorted(list(dic.items()))
    tmp = [None for i in range(4)]
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] = [0] + l

    
    

    ans = 0
    for i in range(len(tmp[0])):
        for j in range(len(tmp[1])):
            for k in range(len(tmp[2])):
                for l in range(len(tmp[3])):
                    weight = base_w * i + (base_w + 1) * j + (base_w + 2) * k + (base_w + 3) * l
                    if weight <= W:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, w = map(int, input().split())
V = [list(map(int, input().split())) for i in range(n)]

w0 = V[0][0]

V_split = [[] for i in range(4)]
for i in range(n):
    V_split[V[i][0] - w0].append(V[i][1])

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



V_split_S = [[0] for i in range(4)]
for i in range(4):
    for j in range(len(V_split[i])):
        V_split_S[i].append(V_split_S[i][-1] + V_split[i][j])





ans = 0

for i in range(min(len(V_split_S[0]), w//w0 + 1)):
    wi = w - w0 * i
    for j in range(min(len(V_split_S[1]), wi//(w0+1) + 1)):
        wj = wi - (w0+1) * j
        for k in range(min(len(V_split_S[2]), wj//(w0+2) + 1)):
            wk = wj - (w0+2) * k
            l = min(len(V_split_S[3]), wk//(w0+3) + 1) - 1
            
            ans = max(ans, V_split_S[0][i] + V_split_S[1][j] + V_split_S[2][k] + V_split_S[3][l])
            
print(ans)

Solution (Python):
N, W = map(int, input().split())
wvs = []
for i in range(N):
  w, v = map(int, input().split())
  wvs.append((w, v))
w0 = wvs[0][0]
vs0 = []
vs1 = []
vs2 = []
vs3 = []
for w, v in wvs:
  if w == w0:
    vs0.append(v)
  if w == w0+1:
    vs1.append(v)
  if w == w0+2:
    vs2.append(v)
  if w == w0+3:
    vs3.append(v)
vs0.sort(reverse=True)
vs1.sort(reverse=True)
vs2.sort(reverse=True)
vs3.sort(reverse=True)

rs = [0]
for i0 in range(len(vs0)+1):
  for i1 in range(len(vs1)+1):
    for i2 in range(len(vs2)+1):
      for i3 in range(len(vs3)+1):
        if w0*i0+(w0+1)*i1+(w0+2)*i2+(w0+3)*i3 <= W:
          r = sum(vs0[:i0])+sum(vs1[:i1])+sum(vs2[:i2])+sum(vs3[:i3])
          rs.append(r)
r = max(rs)
print(r)

Solution (Python):
N,W,*L=map(int,open(0).read().split())
w1=L[0]
l=[[] for _ in range(4)]
for w,v in zip(*[iter(L)]*2):
	l[w-w1].append(v)
l=[sorted(t)[::-1] for t in l]
a,b,c,d=map(len,l)
ans=0
for h in range(a+1):
	for i in range(b+1):
		for j in range(c+1):
			for k in range(d+1):
				if w1*h+(w1+1)*i+(w1+2)*j+(w1+3)*k<=W:
					ans=max(ans,sum(l[0][:h]+l[1][:i]+l[2][:j]+l[3][:k]))
print(ans)

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)

Solution (Python):
import collections
def main():

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

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

    cur = dict()
    cur[0] = 0
    for w in goods:
        temp = cur.copy()
        for w1 in temp:
            w2, v2 = w1, temp[w1]
            for i in range(len(goods[w])):
                w2 += w
                v2 += goods[w][i]
                if w2 <= W:
                    if w2 not in cur:
                        cur[w2] = v2
                    else:
                        cur[w2] = max(cur[w2], v2)
    max_v = 0
    for w in cur:
        max_v = max(max_v, cur[w])
    return max_v

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

Solution (Python):


from itertools import accumulate


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  
    for i in range(0, 2 * N, 2):  
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):  
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
L=[[] for i in range(4)]
L2=[[0] for i in range(4)]
for i in range(n):
  L[l[i][0]-l[0][0]].append(l[i][1])
for i in range(4):
  L[i].sort()
  L[i].reverse()
for i in range(4):
  for j in range(len(L[i])):
    L2[i].append(L2[i][len(L2[i])-1]+L[i][j])
ansL=[]
for i1 in range(len(L2[0])):
  for i2 in range(len(L2[1])):
    for i3 in range(len(L2[2])):
      for i4 in range(len(L2[3])):
        if l[0][0]*i1+(l[0][0]+1)*i2+(l[0][0]+2)*i3+(l[0][0]+3)*i4<=w:
          ansL.append(L2[0][i1]+L2[1][i2]+L2[2][i3]+L2[3][i4])
print(max(ansL))

Solution (Python):
from itertools import accumulate

def chk(samp):
    for i in samp:
        print(samp)

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

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

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




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


for i in range(N):
    wl[w[i]-w[0]].append(v[i])



for i in range(4):
    wl[i].sort(reverse = 1)
    wl[i].insert(0,0)
    


for i in range(4):
    wl[i] = list(accumulate(wl[i]))
    

out = 0


for i,wl0 in enumerate(wl[0]):
   for j,wl1 in enumerate(wl[1]):
       for k,wl2 in enumerate(wl[2]):
           for l,wl3 in enumerate(wl[3]):
               if i*(w[0])+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) > W:
                   pass
               else:
                   out = max(out,wl0+wl1+wl2+wl3)
                   
print(out)

Solution (Python):
from itertools import accumulate
N, W = map(int, input().split())
V = [[] for _ in range(4)]
w0, v0 = map(int, input().split())
V[0].append(v0)
for _ in range(N - 1):
    w, v = map(int, input().split())
    V[w - w0].append(v)
S = []
for v in V:
    v.sort(reverse=True)
    S.append([0] + list(accumulate(v)))
ans = 0
for i, si in enumerate(S[0]):
    for j, sj in enumerate(S[1]):
        for k, sk in enumerate(S[2]):
            for l, sl in enumerate(S[3]):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l > W:
                    continue
                ans = max(ans, si + sj + sk + sl)
print(ans)

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

n, w = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]

dp = [defaultdict(int), defaultdict(int)]
dp[0][0] = 0
for i in range(n):
    wi, vi = obj[i]
    
    dp[(i+1)%2] = dp[i%2].copy()
    for w0 in dp[i%2]:
        
        if w0 + wi <= w:
            dp[(i+1)%2][w0 + wi] = max(dp[(i+1)%2][w0 + wi], dp[i%2][w0] + vi)


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