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())
s = [list(map(int, input().split())) for _ in range(n)]
ss = s[0][0]
s.sort(key = lambda x : x[1], reverse = True)
t = [[] for _ in range(4)]
for u in s:
    t[u[0] - ss].append(u[1])
l1, l2, l3, l4 = len(t[0]) + 1, len(t[1]) + 1, len(t[2]) + 1, len(t[3]) + 1
a, b, = [0] * l1, [0] * l2
c, d, = [0] * l3, [0] * l4
for i in range(1, l1):
    a[i] = t[0][i - 1] + a[i - 1]
for i in range(1, l2):
    b[i] = t[1][i - 1] + b[i - 1]
for i in range(1, l3):
    c[i] = t[2][i - 1] + c[i - 1]
for i in range(1, l4):
    d[i] = t[3][i - 1] + d[i - 1]
ans = 0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for l in range(l4):
                if ss * (i + j + k + l) + (j + 2 * k + 3 * l) <= w:
                    ans = max(ans, a[i] + b[j] + c[k] + d[l])
print(ans)

Solution (Python):

import io

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

Solution (Python):
from collections import defaultdict

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

for k in wv.keys():
    wv[k].sort(reverse=True)

kw = list(wv.keys())
kw.sort()
l = [len(wv[k]) for k in kw]
l = l + (4 - len(l)) * [0]


ans = 0
for i in range(l[0] + 1):
    wi = kw[0] * i
    if W < wi:
        break
    vi = sum(wv[kw[0]][:i])
    if l[1] == 0:
        ans = max(ans, vi)
    for j in range(l[1] + 1):
        if 2 <= len(kw):
            wj = wi + kw[1] * j
            if W < wj:
                break
            vj = vi + sum(wv[kw[1]][:j])
            if l[2] == 0:
                ans = max(ans, vj)
            for k in range(l[2] + 1):
                if 3 <= len(kw):
                    wk = wj + kw[2] * k
                    if W < wk:
                        break
                    vk = vj + sum(wv[kw[2]][:k])
                    if l[3] == 0:
                        ans = max(ans, vk)
                    for m in range(l[3] + 1):
                        if 4 <= len(kw):
                            wm = wk + kw[3] * m
                            if W < wm:
                                break
                            vm = vk + sum(wv[kw[3]][:m])
                            ans = max(ans, vm)
print(ans)

Solution (Python):
n,W = map(int, input().split())
wv = []
w1,v1 = map(int, input().split())
wv.append([0,v1])
for i in range(n-1):
  w,v = map(int, input().split())
  w -= w1
  wv.append([w,v])
dp = [[[-(10 ** 18)] * 301 for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
for key,(wi,vi) in enumerate(wv):
  for num in range(key+1):
    for weight in range(3 * key + 1):
      dp[key+1][num][weight] = max(dp[key+1][num][weight],dp[key][num][weight])
      dp[key+1][num+1][weight+wi] = max(dp[key+1][num+1][weight+wi],dp[key][num][weight] + vi)
ans = 0
for k,i in enumerate(dp):
  for num,v in enumerate(i[:k+1]):
    res = W - num * w1
    if res < 0:
      continue
    ans = max(ans,max(v[:min(res+1,301)]))
print(ans)

Solution (Python):
n,W=map(int,input().split())
w0=0
w,v=[],[]
for i in range(n):
  ww,vv=map(int,input().split())
  if i==0:w0=ww
  w.append(ww-w0)
  v.append(vv)
dp=[[[0]*(n+1) for i in range(3*(n+1))] for i in range(n+1)]

for i in range(n):
  for j in range(3*n):
    for k in range(n):
      if j-w[i]>=0:
        dp[i][j][k+1]=dp[i-1][j-w[i]][k]+v[i]
      dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])

ans=0
for i in range(n):
  for j in range(3*n):
    for k in range(n+1):
      if j+k*w0<=W:
        ans=max(dp[i][j][k],ans)
print(ans)

Solution (Python):
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            if W < a*w+b*x+c*y:
                break
            z = min((W-a*w-b*x-c*y)//d, len(dd[d]))
            val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
            ans = max(ans, val)
print(ans)

Solution (Python):
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
                ans = max(ans, val)
print(ans)

Solution (Python):
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

for k in dd.keys():
    dd[k].sort(reverse=True)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = sum(dd[a][:w])+sum(dd[b][:x]) + \
                    sum(dd[c][:y])+sum(dd[d][:z])
                ans = max(ans, val)
print(ans)

Solution (Python):
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

for k in dd.keys():
    dd[k].sort(reverse=True)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = sum(dd[a][:w])+sum(dd[b][:x]) + \
                    sum(dd[c][:y])+sum(dd[d][:z])
                ans = max(ans, val)
print(ans)

Solution (Python):
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split()))for _ in range(n)])
min_w = min(weights)-1
weights = [weight-min_w for weight in weights]
W_MAX = 4*200
dp = [[0]*(W_MAX+1) for _ in range(n+1)]
for i in range(1, n+1):
    for k in reversed(range(1, n+1)):
        for j in range(1, W_MAX+1):
            if j-weights[i-1] < 0:
                continue
            dp[k][j] = max(dp[k][j], dp[k-1][j-weights[i-1]]+values[i-1])

ans = 0
for k in range(n+1):
    w_max = min(w-k*min_w, W_MAX)
    if w_max < 0:
        continue
    ans = max(ans, dp[k][w_max])
print(ans)

Solution (Python):
N,W = map(int,input().split())
v1 = []
v2 = []
v3 = []
v4 = []
w1,v = map(int,input().split())
v1.append(v)
for i in range(N-1):
    w,v = map(int,input().split())
    if w == w1:
        v1.append(v)
    elif w == w1 + 1:
        v2.append(v)
    elif w == w1 + 2:
        v3.append(v)
    elif w == w1 + 3:
        v4.append(v)
v1.sort(reverse=True)
v2.sort(reverse=True)
v3.sort(reverse=True)
v4.sort(reverse=True)

l1 = len(v1)
l2 = len(v2)
l3 = len(v3)
l4 = len(v4)
ans = 0
for i in range(l1+1):
    for j in range(l2+1):
        for k in range(l3+1):
            for l in range(l4+1):

                if i*w1 + j*(w1+1) + k*(w1+2) + l*(w1+3) <= W:
                    temp = sum(v1[:i]) + sum(v2[:j]) + sum(v3[:k]) + sum(v4[:l])
                    ans = max(ans,temp)
print(ans)

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

w1 = item[0][0]
V = [[] for _ in range(4)]
for w, v in item:
    V[w - w1].append(v)
for i in range(4):
    V[i].sort(reverse=True)

cnt = [0] * 4
for i in range(4):
    cnt[i] = len(V[i])

ans = 0
for i in range(cnt[0] + 1):
    S0 = sum(V[0][:i])
    W0 = i * w1
    for j in range(cnt[1] + 1):
        S1 = sum(V[1][:j])
        W1 = j * (w1 + 1)
        for k in range(cnt[2] + 1):
            S2 = sum(V[2][:k])
            W2 = k * (w1 + 2)
            for l in range(cnt[3] + 1):
                S3 = sum(V[3][:l])
                W3 = l * (w1 + 3)
                if W0 + W1 + W2 + W3 <= W:
                    ans = max(ans, S0 + S1 + S2 + S3)

print(ans)

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

w1 = item[0][0]
V = [[] for _ in range(4)]
for w, v in item:
    V[w - w1].append(v)
for i in range(4):
    V[i].sort(reverse=True)

cnt = [0] * 4
for i in range(4):
    cnt[i] = len(V[i])

ans = 0
for i in range(cnt[0] + 1):
    S0 = sum(V[0][:i])
    W0 = i * w1
    for j in range(cnt[1] + 1):
        S1 = sum(V[1][:j])
        W1 = j * (w1 + 1)
        for k in range(cnt[2] + 1):
            S2 = sum(V[2][:k])
            W2 = k * (w1 + 2)
            for l in range(cnt[3] + 1):
                S3 = sum(V[3][:l])
                W3 = l * (w1 + 3)
                if W0 + W1 + W2 + W3 <= W:
                    ans = max(ans, S0 + S1 + S2 + S3)

print(ans)

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

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

pre_dp = defaultdict(lambda: 0)
pre_dp[0] = 0

for i in range(1, n+1):
    cur_dp = defaultdict(lambda: 0)
    w_i, v_i = wv[i-1]

    keys = sorted(pre_dp.keys())
    for k in keys:
        cur_dp[k] = max(cur_dp[k], pre_dp[k])
        if k + w_i <= W:
            big = max(pre_dp[k + w_i], pre_dp[k] + v_i)
            cur_dp[k+w_i] = big
    pre_dp = cur_dp
ans = 0
for w, v in cur_dp.items():
    if w <= W:
        ans = max(ans, v)

print(ans)

Solution (Python):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
mw = wv[0][0]
wv.sort(key=lambda x: -x[1])
values = [[] for _ in range(4)]
for w, v in wv:
    values[w-mw].append(v)


def solve(n, w, c):
    if n >= 4 or w >= W or c >= N:
        return 0
    r = 0
    for i in range(len(values[n])+1):
        cw = w + (mw + n) * i
        cc = c + i
        if cw <= W and cc <= N:
            r = max(r, sum(values[n][0:i]) + solve(n+1, cw, cc))
    return r


print(solve(0, 0, 0))

Solution (Python):
N,W = map(int,input().split())
tmpv = [[] for _ in range(4)]
w1 = None
for i in range(N):
    tw, tv = map(int,input().split())
    if i==0:
        w1 = tw
        tmpv[0].append(tv)
    else:
        tmpv[tw-w1].append(tv)

v = []
for tv in tmpv:
    v.append(sorted(tv, reverse=True)+[0])
    
ans = 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])):
        tw = w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l
        tv = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])
        if tw<=W:
          ans = max(ans, tv)
print(ans)

Solution (Python):
n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)


for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w:
        w1.append(b)
    if a == w+1:
        w2.append(b)
    if a == w+2:
        w3.append(b)
    if a == w+3:
        w4.append(b)
        

for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n,W = map(int, input().split())
    w,v = [], []
    for i in range(n):
        a,b = map(int, input().split())
        if i == 0:
            w.append(a)
        else:
            w.append(a - w[0])
        v.append(b)
    
    base = w[0]
    w[0] = 0
    w0, w1, w2, w3 = [], [], [], []
    for i in range(n):
        if w[i] == 0:
            w0.append(v[i])
        if w[i] == 1:
            w1.append(v[i])
        if w[i] == 2:
            w2.append(v[i])
        if w[i] == 3:
            w3.append(v[i])
    w0.sort(reverse=1)
    w1.sort(reverse=1)
    w2.sort(reverse=1)
    w3.sort(reverse=1)
    w0 = [0] + w0
    w1 = [0] + w1
    w2 = [0] + w2
    w3 = [0] + w3
    w0 = list(accumulate(w0))
    w1 = list(accumulate(w1))
    w2 = list(accumulate(w2))
    w3 = list(accumulate(w3))

    res = 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 base*(i+j+k+l) + j + k*2 + l*3 <= W:
                        res = max(res, w0[i]+w1[j]+w2[k]+w3[l])
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
N, W, *WV = map(int, open(0).read().split())

C = {0: 0}
for v, w in zip(*[reversed(WV)] * 2):
    for x, y in C.copy().items():
        if x + w <= W:
            C[x + w] = max(C.get(x + w, 0), y + v)

print(max(C.values()))

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]

w1=wv[0][0]
wv.sort()
lst=[[],[],[],[]]
for i in range(n):
    w,v=wv[i]
    lst[w-w1].append(v)

ruilst=[]
for i in range(4):
    ruilst.append(ruiseki(lst[i][::-1]))


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

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

dp=[[-float('inf')]*101*400 for i in range(n+1)]
dp[0][0]=0

kijun=wv[0][0]
for i in range(n):
    for j in range(101*400):
        if dp[i][j]!=-float('inf'):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            ko,a=j//400,j%400
            dp[i+1][(ko+1)*400+a+wv[i][0]-kijun]=max(dp[i+1][(ko+1)*400+a+wv[i][0]-kijun],dp[i][j]+wv[i][1])

ans=0
for i in range(101*400):
    ko,a=i//400,i%400
    if ko*kijun+a<=w:
        ans=max(ans,dp[n][i])
print(ans)

Solution (Python):
from collections import defaultdict
N,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(N)]
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):
import itertools
from collections import defaultdict

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

for i in d:
    d[i] = list(itertools.accumulate(sorted(d[i], reverse=True)))
mm = min(d)

ans = 0
for t in itertools.product(range(len(d[mm]) + 1), range(len(d[mm + 1]) + 1),
                           range(len(d[mm + 2]) + 1), range(len(d[mm + 3]) + 1)):
    if sum((mm + i) * t[i] for i in range(4)) > W:
        continue
    ans = max(ans, sum(d[mm + i][t[i] - 1] if t[i] else 0 for i in range(4)))
print(ans)

Solution (Python):

n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)
for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)
    
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)

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

w0,v0 = map(int,input().split())
vlist = [[v0],[],[],[]]

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

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

m = 0
S = [[0],[0],[0],[0]]
for i in range(4):
    for j in range(len(vlist[i])):
        S[i].append(S[i][-1]+vlist[i][j])

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



print(m)

Solution (Python):
import sys
from operator import itemgetter

rl = sys.stdin.readline


def solve():
    N, W = map(int, rl().split())
    w1, w2, w3, w4 = [[0, 0]], [[0, 0]], [[0, 0]], [[0, 0]]
    w1.append(list(map(int, rl().split())))
    min_w = w1[1][0]
    for _ in range(N - 1):
        w, v = map(int, rl().split())
        d = w - min_w
        if d == 0:
            w1.append([w, v])
        elif d == 1:
            w2.append([w, v])
        elif d == 2:
            w3.append([w, v])
        else:
            w4.append([w, v])
    w1.sort(key=itemgetter(1), reverse=True)
    w2.sort(key=itemgetter(1), reverse=True)
    w3.sort(key=itemgetter(1), reverse=True)
    w4.sort(key=itemgetter(1), reverse=True)
    
    ans = 0
    for i in range(len(w1)):
        w_tmp1, v_tmp1 = 0, 0
        for j in range(i):
            w_tmp1 += w1[j][0]
            v_tmp1 += w1[j][1]
        for j in range(len(w2)):
            w_tmp2, v_tmp2 = w_tmp1, v_tmp1
            for k in range(j):
                w_tmp2 += w2[k][0]
                v_tmp2 += w2[k][1]
            for k in range(len(w3)):
                w_tmp3, v_tmp3 = w_tmp2, v_tmp2
                for l in range(k):
                    w_tmp3 += w3[l][0]
                    v_tmp3 += w3[l][1]
                for l in range(len(w4)):
                    w_tmp4, v_tmp4 = w_tmp3, v_tmp3
                    for m in range(l):
                        w_tmp4 += w4[m][0]
                        v_tmp4 += w4[m][1]
                    if w_tmp4 <= W:
                        ans = max(ans, v_tmp4)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from operator import itemgetter

rl = sys.stdin.readline


def solve():
    N, W = map(int, rl().split())
    w1, w2, w3, w4 = [[0, 0]], [[0, 0]], [[0, 0]], [[0, 0]]
    w1.append(list(map(int, rl().split())))
    min_w = w1[1][0]
    for _ in range(N - 1):
        w, v = map(int, rl().split())
        d = w - min_w
        if d == 0:
            w1.append([w, v])
        elif d == 1:
            w2.append([w, v])
        elif d == 2:
            w3.append([w, v])
        else:
            w4.append([w, v])
    w1.sort(key=itemgetter(1), reverse=True)
    w2.sort(key=itemgetter(1), reverse=True)
    w3.sort(key=itemgetter(1), reverse=True)
    w4.sort(key=itemgetter(1), reverse=True)
    
    ans = 0
    for i in range(len(w1)):
        w_tmp1, v_tmp1 = 0, 0
        for j in range(i):
            w_tmp1 += w1[j][0]
            v_tmp1 += w1[j][1]
        for j in range(len(w2)):
            w_tmp2, v_tmp2 = w_tmp1, v_tmp1
            for k in range(j):
                w_tmp2 += w2[k][0]
                v_tmp2 += w2[k][1]
            for k in range(len(w3)):
                w_tmp3, v_tmp3 = w_tmp2, v_tmp2
                for l in range(k):
                    w_tmp3 += w3[l][0]
                    v_tmp3 += w3[l][1]
                for l in range(len(w4)):
                    w_tmp4, v_tmp4 = w_tmp3, v_tmp3
                    for m in range(l):
                        w_tmp4 += w4[m][0]
                        v_tmp4 += w4[m][1]
                    if w_tmp4 <= W:
                        ans = max(ans, v_tmp4)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n,W=map(int,input().split())
wv=[[]for _ in range(4)]
for i in range(n):
	w,v=map(int,input().split())
	if i==0:
		r=w
		wv[0].append(v)
	else:
		wv[w-r].append(v)
for i in range(4):
	wv[i].sort(reverse=True)
	for j in range(len(wv[i])-1):
		wv[i][j+1]+=wv[i][j]
	wv[i].insert(0,0)
ans=0
for i in range(len(wv[0])):
	for j in range(len(wv[1])):
		for k in range(len(wv[2])):
			for l in range(len(wv[3])):
				p=wv[0][i]+wv[1][j]+wv[2][k]+wv[3][l]
				if i*r+j*(r+1)+k*(r+2)+l*(r+3)<=W:
					ans=max(ans,p)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from bisect import bisect_right

def main():
    n,w = map(int,input().split())
    minw,u = map(int,input().split())
    item = {minw:[u],minw + 1:[],minw + 2:[], minw + 3:[]}
    for _ in range(n - 1):
        wei,u = map(int,input().split())
        item[wei].append(u)
    
    l = [0] * 4
    keys = sorted(item.keys())
    i = 0
    for k in keys:
        item[k].sort(reverse = True)
        l[i] = len(item[k])
        i += 1
    
    X = set()
    for i in range(l[0] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw][i - 1]
        cumsumx = cumsum
        for j in range(l[1] + 1):
            weight = minw * i + (minw + 1) * j 
            if j != 0:
                cumsumx += item[minw + 1][j - 1]
            if weight <= w:
                X.add((weight, cumsumx))

    Y = []
    for i in range(l[2] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw + 2][i - 1]
        cumsumy = cumsum
        for j in range(l[3] + 1):
            weight = (minw + 2) * i + (minw + 3) * j
            if j != 0:
                cumsumy += item[minw  + 3][j - 1]
            if weight <= w:
                Y.append((weight, cumsumy))
    
    Y.sort(key = lambda x:x[0])
    Yw = [0] * len(Y)
    cummax = [0] * len(Y)
    for i in range(len(Y)):
        if i == 0:
            cummax[i] = Y[i][1]
            Yw[i] = Y[i][0]
        else:
            cummax[i] = max(cummax[i - 1],Y[i][1])
            Yw[i] = Y[i][0]
    
    ans = 0
    for x in X:
        wei,va = x
        idx = bisect_right(Yw,w - wei)
        if idx == 0:
            continue
        else:
            ans = max(ans,cummax[idx - 1] + va)
    
    print(ans)
    
    
if __name__=='__main__':
    main()

Solution (Python):
N,W=map(int,input().split())
l=[0]*4
s=[[] for i in range(4)]
for i in range(N):
    w,v=map(int,input().split())
    if w in l:
        s[l.index(w)].append(v)
    else:
        for i in range(4):
            if l[i]==0:
                l[i]=w
                s[i].append(v)
                break
g=[[0] for i in range(4)]
for i in range(4):
    s[i].sort(reverse=1)
    t=0
    for j in s[i]:
        t+=j
        g[i].append(t)
a=0
for i in range(len(g[0])):
    for j in range(len(g[1])):
        for k in range(len(g[2])):
            for m in range(len(g[3])):
                if i*l[0]+j*l[1]+k*l[2]+m*l[3]>W:
                    continue
                t=g[0][i]+g[1][j]+g[2][k]+g[3][m]
                if t>a:
                    a=t
print(a)

Solution (Python):





import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


N, W = read_ints()
w, v = read_col(N, 2)

from collections import defaultdict
dp = defaultdict(lambda: -1)


def f(i, j):  
    if dp[i, j] != -1:
        return dp[i, j]
    if i == -1:
        return 0
    if j - w[i] < 0:
        return f(i - 1, j)

    ret = max(f(i - 1, j - w[i]) + v[i], f(i - 1, j))
    dp[i, j] = ret
    return ret


print(f(N - 1, W))

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

for _ in range(N):
    wv.append(tuple(map(int, input().split())))










memo = {}

def dfs(i, j):
    if (i,j) in memo:
        return memo[(i,j)]

    if i < 0 or j <= 0:
        return 0

    ret = 0
    wi, vi = wv[i]
    if j-wi < 0:
        ret = dfs(i-1, j)
    else:
        ret = max(dfs(i-1, j), dfs(i-1, j-wi) + vi)

    memo[(i,j)] = ret

    return ret

print(dfs(N-1, W))

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())
ws=w[0]
V=[[] for i in range(4)]
for i in range(n):
  V[w[i]-ws].append(v[i])
V[0].sort(reverse=True)
V[1].sort(reverse=True)
V[2].sort(reverse=True)
V[3].sort(reverse=True)
VV=[[0] for i in range(4)]
for i in range(4):
  for j in range(len(V[i])):
    VV[i].append(VV[i][-1]+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*ws+j*(ws+1)+k*(ws+2)+l*(ws+3)>W:
          break
        if VV[0][i]+VV[1][j]+VV[2][k]+VV[3][l]>ans:
          ans=VV[0][i]+VV[1][j]+VV[2][k]+VV[3][l]
print(ans)

Solution (Python):
n, W = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]

base = a[0][0]
s = [[] for _ in range(4)]
for w, v in a:
    s[w-base].append(v)
for i in range(4):
    s[i].sort(reverse=True)

length = [len(s[i]) for i in range(4)]
cum = [[] for _ in range(4)]
for i in range(4):
    cum[i] = [0 for _ in range(length[i]+1)]
    for j in range(length[i]):
        cum[i][j+1] = cum[i][j] + s[i][j]

ans = 0
for i in range(length[0]+1):
    for j in range(length[1]+1):
        for k in range(length[2]+1):
            for l in range(length[3]+1):
                weight = (i+j+k+l) * base + j + 2*k + 3*l
                if weight <= W:
                    ans = max(ans, cum[0][i] + cum[1][j] + cum[2][k] + cum[3][l])
print(ans)

Solution (Python):


def saiki(value,HP,num):
    if num==0:
        
        value+=wa[0][min(HP//base,len(wa[0])-1)]
        ans.append(value)
    else:
        for i in range(len(wa[num])):
            if HP-(num+base)*i>=0:
                saiki(value+wa[num][i],HP-(num+base)*i,num-1)
            else:
                break
    return


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

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

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    lis[w-base].append(v)

lis=list(map(lambda x:sorted(x, reverse=True),lis))

wa=[[0] for i in range(4)]

for i in range(len(wa)):
    for item in lis[i]:
        wa[i].append(wa[i][-1]+item)



ans=[]
saiki(0,W,3)
    

print(max(ans))

Solution (Python):
import  numpy as np
N, W, *L = map(int, open(0).read().split())
M = 3*(N-1)+1
dp = np.zeros((M,N+1),np.int64)
for w,v in zip(*[iter(L)]*2):
  w -= L[0]
  dp[w:,1:] = np.maximum(dp[w:,1:], dp[:M-w,:N]+v)

ans = 0
for i in range(N+1):
  m = i*L[0]
  if m>W:
    continue
  m = min(W-m,M-1)
  ans = max(ans, dp[m,i])
print(ans)

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])
w1 = wv[0][0]
dp = [[[0] * (N + 1) for _ in range(4 * N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = wv[i - 1]
    w -= (w1 - 1)
    for j in range(4 * N + 1):
        for k in range(1, N + 1):
            if j - w >= 0:
                dp[i][j][k] = max(dp[i - 1][j - w][k - 1] + v, dp[i - 1][j][k])
            else:
                dp[i][j][k] = dp[i - 1][j][k]
ans = 0
for i in range(N + 1):
    for j in range(4 * N + 1):
        for k in range(N + 1):
            if W - (w1 - 1) * k >= j:
                ans = max(ans, dp[i][j][k])

print(ans)

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

value_table = [[] for i in range(4)]
for i in range(N):
    w, v = map(int,input().split())
    if i == 0:
        w1 = w
    value_table[w-w1] += [v]

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

ans = 0
value_table_ruiseki = [[0] for i in range(4)]
for i in range(4):
    for v in value_table[i]:
        value_table_ruiseki[i] += [value_table_ruiseki[i][-1] + v]

ans = 0
for i, iv in enumerate(value_table_ruiseki[0]):
    for j, jv in enumerate(value_table_ruiseki[1]):
        for k, kv in enumerate(value_table_ruiseki[2]):
            for ell, ellv in enumerate(value_table_ruiseki[3]):
                weight = i*w1 + j*(w1+1) + k*(w1+2) + ell*(w1+3)
                value = iv + jv + kv + ellv
                if weight <=W:
                    ans = max(ans, value)

print(ans)

Solution (Python):
from collections import defaultdict

n, W = 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:
    for k in sorted(dp.keys(), reverse=True):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)

ans = max(dp.values())
print(ans)