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):
from collections import defaultdict

n, w = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    wi, vi = map(int, input().split())
    d[wi].append(vi)
for key in d.keys():
    di = d[key]
    di.sort(reverse=True)
    a = [0]
    for i in di:
        a.append(a[-1] + i)
    d[key] = a
keys = list(d.keys())
for i in range(4 - len(keys)):
    key = max(keys) + i + 1
    d[key] = [0]
    keys.append(key)
ans = 0
for i in range(min(w // keys[0] + 1, len(d[keys[0]]))):
    wi = w - keys[0] * i
    ai = d[keys[0]][i]
    for j in range(min(wi // keys[1] + 1, len(d[keys[1]]))):
        wj = wi - keys[1] * j
        aj = d[keys[1]][j]
        for k in range(min(wj // keys[2] + 1, len(d[keys[2]]))):
            wk = wj - keys[2] * k
            ak = d[keys[2]][k]
            idx = min(wk // keys[3], len(d[keys[3]]) - 1)
            ans = max(ans, ai + aj + ak + d[keys[3]][idx])
print(ans)

Solution (Python):
N,W = map(int,input().split())
wv = {}
for i in range(N):
    w,v = map(int,input().split())
    if w not in wv.keys():
        wv[w] = []
    wv[w].append(v)

for w in wv.keys():
    wv[w] = sorted(wv[w],reverse=True)

wv_ruiseki = {}
for w in wv.keys():
    wv_ruiseki[w] = [0,wv[w][0]]
    for i in range(2,len(wv[w])+1):
        wv_ruiseki[w].append(wv_ruiseki[w][i-1] + wv[w][i-1])


w = []
for i in wv.keys():
    w.append(i)

ans = 0
if len(w) == 1:

    for i in range(len(wv[w[0]])+1):
        if w[0]*i <= W:
            ans = max(ans , wv_ruiseki[w[0]][i])
elif len(w) == 2:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            if w[0]*i + w[1]*j <= W:
                ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j])

elif len(w) == 3:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                if w[0]*i + w[1]*j + w[2]*k <= W:
                    ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k])
elif len(w) == 4:
    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                for t in range(len(wv[w[3]])+1):
                    if w[0]*i + w[1]*j + w[2]*k + w[3]*t <= W:
                        ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k] + wv_ruiseki[w[3]][t])


print(ans)

Solution (Python):




N,W = map(int,input().split())
WV = [[int(x) for x in input().split()] for _ in range(N)]
w1 = WV[0][0]
V = [[],[],[],[]]
Vcum = [[0],[0],[0],[0]]

for w,v in WV:
  V[w-w1].append(v)

for i in range(4):
  s = 0
  V[i].sort(reverse = True) 
  for x in V[i]:
    s += x
    Vcum[i].append(s)
    

answer = 0
for a in range(len(V[0])+1):
  for b in range(len(V[1])+1):
    for c in range(len(V[2])+1):
      w = w1*a + (w1+1)*b + (w1+2)*c
      if w > W:
        break
      d = min((W-w)//(w1+3),len(V[3]))
      x = Vcum[0][a] + Vcum[1][b] + Vcum[2][c] + Vcum[3][d]
      answer = max(answer,x)
print(answer)

Solution (Python):



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

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


w_min = L[0][0]


M = [[], [], [], []]
for w, v in L:
      M[w - w_min].append(v)


M0 = sorted(M[0], reverse=True)
M1 = sorted(M[1], reverse=True)
M2 = sorted(M[2], reverse=True)
M3 = sorted(M[3], reverse=True)

ans = 0

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

print(ans)

Solution (Python):
N,W = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

lic = [[],[],[],[]]
mi = li[0][0]
for w,v in li:
  lic[w-mi].append(v)

[ lis.sort() for lis in lic ]
[ lis.reverse() for lis in lic ]


for j in range(4):
  pli = lic[j]
  for i in range( len(pli) - 1 ):
    pli[i+1] += pli[i]
for i in range(4):
  tmp = [0]
  tmp.extend(lic[i])
  lic[i] = tmp 
    

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

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

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

from collections import defaultdict
DP = defaultdict(int)
DP[0]=0

for w,v in S:
    for w2 in sorted(DP.keys(),reverse=True):
        if w+w2<=W:
            DP[w+w2]=max(DP[w+w2],DP[w2]+v)

print(max(DP.values()))

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math

mod = 10**9+7

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

w_sum = [0 for i in range(N+1)]
v_sum = [0 for i in range(N+1)]

w.insert(0,0)
v.insert(0,0)

for i in range(N):
    w_sum[i+1] = w_sum[i]+w[i+1]
    v_sum[i+1] = v_sum[i]+v[i+1]


nap_memo = {}

def nap(i,W2):
    key = str(i)+":"+str(W2)
    if key in nap_memo:
        return nap_memo[key]
    elif i == 0:
        r = 0
    elif W2 < w[0]:
        r = 0
    elif W2 < w[i]:
        r = nap(i-1,W2)
    elif w_sum[i] <= W2:
        r = v_sum[i]
    else:
        r = max(nap(i-1,W2-w[i])+v[i], nap(i-1,W2))

    nap_memo[key] = r
    return r


print(nap(N,W))

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

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

values = [[] for _ in range(4)]

values[0].append(v)

for _ in range(N-1):
    x, y = map(int, input().split())
    values[x-w].append(y)

n = [0]*4
for i in range(4):
    n[i] = len(values[i])
    values[i].sort(reverse=1)

ans = 0
ans0 = 0
ans1 = 0
ans2 = 0
for n0 in range(n[0]+1):
    if n0 > 0:
        ans0 += values[0][n0-1]
    if n0 * w > W:
        break
    for n1 in range(n[1]+1):
        if n1 > 0:
            ans1 += values[1][n1-1]
        else:
            ans1 = 0
        if n0 * w + n1 * (w+1) > W:
            break
        for n2 in range(n[2]+1):
            ww = n0 * w + n1 * (w+1) + n2 * (w+2)
            if n2 > 0:
                ans2 += values[2][n2-1]
            else:
                ans2 = 0
            if ww > W:
                break
            n3 = (W - ww) // (w+3)
            ans = max(ans, ans0+ans1+ans2+sum(values[3][:n3]))

print(ans)

Solution (Python):
import functools
from collections import*
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return max(d.values())
N,W=map(int,input().split())   
d=defaultdict(int)
d[0]=0
print(Knapsack(N,W))

Solution (Python):
N,W=map(int,input().split())
from collections import*
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for k,b in d.copy().items():
        if k+w<=W:
            d[k+w]=max(d[k+w],b+v)
print(max(d.values()))

Solution (Python):
from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            if nums[i] >= 1:
                value += items[weights[i]][nums[i] - 1]
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

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

for v in items.values():
    v.sort(reverse=True)
    for i in range(1, len(v)):
        v[i] = v[i - 1] + v[i]

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(min(W // w, len(items[w])))
print(dfs([]))

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 *

N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for p,q in d.copy().items():
        if p+w<=W:
            d[p+w]=max(d[p+w],q+v)
print(max(d.values()))

Solution (Python):
from collections import *

N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    c=d.copy()
    for p,q in c.items():
        if p+w<=W:
            d[p+w]=max(d[p+w],q+v)
print(max(d.values()))

Solution (Python):
from itertools import accumulate
n, W = [int(item) for item in input().split()]
wv = [[] for _ in range(4)]
for i in range(n):
    w, v = [int(item) for item in input().split()]
    if i == 0:
        w1 = w
    wv[w-w1].append(v)
for i in range(4):
    wv[i] = sorted(wv[i], reverse=True)
    wv[i] = [0] + list(accumulate(wv[i]))

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])):
                if j*1 + k*2 + l*3 <= W - w1*(i+j+k+l):
                    ans = max(ans, wv[0][i] + wv[1][j] + wv[2][k] + wv[3][l])
print(ans)

Solution (Python):
import itertools

def main():
    n,w = [int(i) for i in input().split()]
    vals = [[], [], [], []]

    w0, v0 = [int(i) for i in input().split()]
    vals[0].append(v0)

    for i in range(n - 1):
        wi, vi = [int(i) for i in input().split()]
        vals[wi-w0].append(vi)

    vals[0].sort(reverse=True)
    vals[1].sort(reverse=True)
    vals[2].sort(reverse=True)
    vals[3].sort(reverse=True)

    ans = 0
    for i, j, k, l in itertools.product(range(len(vals[0])+1), range(len(vals[1])+1), range(len(vals[2])+1), range(len(vals[3])+1)):
        if i * w0 + j * (w0 + 1) + k * (w0 + 2) + l * (w0 + 3) <= w:
            ans = max(ans, sum(vals[0][:i]) + sum(vals[1][:j]) + sum(vals[2][:k]) + sum(vals[3][:l]))

    print(ans)

main()

Solution (Python):


import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    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)

    for i in range(4):
        V[i] = list(accumulate([0] + sorted(V[i], key=lambda x: -x)))

    ans = 0
    for i in range(len(V[0])):
        for j in range(len(V[1])):
            for k in range(len(V[2])):
                weight = w0 * i + (w0 + 1) * j + (w0 + 2) * k
                if weight <= W:
                    l  = min(len(V[3]) - 1, (W - weight) // (w0 + 3))
                    ans = max(ans, V[0][i] + V[1][j] + V[2][k] + V[3][l])

    return ans


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

Solution (Python):
import sys
from collections import defaultdict, deque

def main():
    input = sys.stdin.readline
    N, W = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(N)]

    d = defaultdict(lambda: 0)
    q = deque()
    for a in A:
        while len(q) > 0:
            w0, v0 = q.popleft()

            w1 = w0 + a[0]
            v1 = v0 + a[1]

            if w1 <= W:
                d[w1] = max(d[w1], v1)

            d[w0] = max(d[w0], v0)

        if a[0] <= W:
            q.append(a)

        for key in d.keys():
            q.append((key, d[key]))

    ans = 0
    for key in d.keys():
        ans = max(ans, d[key])

    return ans


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

Solution (Python):
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))

Solution (Python):
def simple_knapsack(N: int, W: int, items: list) -> int:
    w0 = items[0][0]
    d = {w0+i: [] for i in range(4)}
    for w, v in items:
        d[w].append(v)

    s = {}
    for k, values in d.items():
        s[k] = [0] * (len(values)+1)
        for i, v in enumerate(sorted(values, key=lambda x: -x)):
            s[k][i + 1] = s[k][i] + v

    w0, w1, w2, w3 = w0, w0 + 1, w0 + 2, w0 + 3

    max_value = 0
    for i1 in range(len(s[w0])):
        if W < w0 * i1:
            break
        for i2 in range(len(s[w1])):
            if W < w0 * i1 + w1 * i2:
                break
            for i3 in range(len(s[w2])):
                if W < w0 * i1 + w1 * i2 + w2 * i3:
                    break
                for i4 in range(len(s[w3])):
                    if W < w0 * i1 + w1 * i2 + w2 * i3 + w3 * i4:
                        break
                    max_value = max(
                        max_value, s[w0][i1] + s[w1][i2] + s[w2][i3] + s[w3][i4])

    return max_value


if __name__ == "__main__":
    N = 0
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    ans = simple_knapsack(N, W, items)
    print(ans)

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

N,W = map(int,input().split())
info = []
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    w = w - (w1-1)
    info.append((w,v))




dp = [[[0]*(N+1) for _ in range(400)] for _ in range(N+1)]
for i in range(1,N+1):
    w = info[i-1][0]; v = info[i-1][1]
    for j in range(400):
        for k in range(1,N+1):
            dp[i][j][k] = dp[i-1][j][k]
            if j - w >= 0:
                if dp[i][j][k] < dp[i-1][j-w][k-1] + v:
                    dp[i][j][k] = dp[i-1][j-w][k-1] + v
ans = -1
for j in range(400):
    for k in range(N+1):
        if not((w1-1)*k + j <= W):
            continue
        if dp[N][j][k] > ans:
            ans = dp[N][j][k]
print(ans)

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

dp = {}
dp[0] = 0
for w, v in a:
    pre_dp = dp.copy()
    for pw, pv in pre_dp.items():
        if pw + w <= W:
            dp[pw + w] = max(dp.get(pw + w, 0), pv + v)

print(max(dp.values()))

Solution (Python):
n,W = map(int,input().split())
a = {}
for i in range(n):
    w,v = map(int,input().split())
    a.setdefault(w, []).append(v)

we = [0]*4
va = []
num = [0]*4
for i,[k,v] in enumerate(a.items()):
    we[i] = k
    va.append(sorted(v,reverse=True))
    num[i] = len(v)
for i in range(4-len(va)):
    va.append([0])

ans = -float('inf')
for i in range(max(1,num[0]+1)):
    for j in range(max(1,num[1]+1)):
        for k in range(max(1,num[2]+1)):
            for l in range(max(1,num[3]+1)):
                if we[0]*i + we[1]*j + we[2]*k + we[3]*l <= W:
                    total = 0
                    for im,m in enumerate([i,j,k,l]):
                        total += sum(va[im][:m])
                    ans = max(ans, total)
print(ans)

Solution (Python):
from collections import deque
N,W=map(int,input().split())
w1,v1=map(int,input().split())
V=[[v1],[],[],[]]
for i in range(N-1):
    w,v=map(int,input().split())
    V[w-w1].append(v)
for i in range(4):
    V[i].sort(reverse=True)
W0=W
V0=0
ans=0
for a in range(-1,len(V[0])):
    if a!=-1:
        W0-=w1
        if W0<0:
            break
        V0+=V[0][a]
    W1=W0
    V1=V0
    ans=max(ans,V0)
    for b in range(-1,len(V[1])):
        if b!=-1:
            W1-=w1+1
            if W1<0:
                break
            V1+=V[1][b]
        W2=W1
        V2=V1
        ans=max(ans,V1)
        for c in range(-1,len(V[2])):
            if c!=-1:
                W2-=w1+2
                if W2<0:
                    break
                V2+=V[2][c]
            ans=max(ans,V2)
            if W2//(w1+3)>0:
                ans=max(ans,V2+sum(V[3][0:(W2//(w1+3))]))
print(ans)

Solution (Python):
def main():
    N, W = map(int, input().split())
    dp = {0: 0}
    for i in range(N):
        w, v = map(int, input().split())
        nxt = {}
        for k in dp:
            if k+w <= W:
                nxt[k+w] = max(dp[k] + v, dp[k+w] if k+w in dp else 0)
        dp.update(nxt)
    ans = 0
    for k in dp:
        ans = max(ans, dp[k])
    print(ans)


if __name__ == "__main__":
    main()

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

ans = dict()
ans[0] = 0
for w, v in item:
    next = dict()
    for temp_w, temp_v in ans.items():
        if temp_w + w <= max_w:
            if temp_w + w not in next.keys():
                next[temp_w + w] = temp_v + v
            else:
                if temp_v + v > next[temp_w + w]:
                    next[temp_w + w] = temp_v + v
    
    for x, y in next.items():
        if x not in ans.keys():
            ans[x] = y
        else:
            if y > ans[x]:
                ans[x] = y


res = 0
for x, y in ans.items():
    res = max(res, y)

print(res)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






""""
n,T = LI()
ans = 0
t = LI()
for i in range(n-1):
    ans += min(T,t[i+1]-t[i])
ans += T
print(ans)
"""


n,w = LI()
g = LIR(n)
l = [[] for i in range(4)]
for W,v in g:
    l[W-g[0][0]].append(v)
    l[W-g[0][0]].sort(reverse = True)
l0 = len(l[0])
l1 = len(l[1])
l2 = len(l[2])
l3 = len(l[3])
for i in range(l0-1):
    l[0][i+1] += l[0][i]
l[0].insert(0,0)
for i in range(l1-1):
    l[1][i+1] += l[1][i]
l[1].insert(0,0)
for i in range(l2-1):
    l[2][i+1] += l[2][i]
l[2].insert(0,0)
for i in range(l3-1):
    l[3][i+1] += l[3][i]
l[3].insert(0,0)
ans = 0
for i in range(l0+1):
    for j in range(l1+1):
        for k in range(l2+1):
            for m in range(l3+1):
                if i*g[0][0]+j*(g[0][0]+1)+k*(g[0][0]+2)+m*(g[0][0]+3) <= w:
                    ans = max(ans,l[0][i]+l[1][j]+l[2][k]+l[3][m])
print(ans)

Solution (Python):
N,W = map(int,input().split())
L = []
for i in range(N):
  L.append(list(map(int,input().split())))
Vmax = 0
w_1 = []
w_2 = []
w_3 = []
w_4 = []
for i in range(N):
  if L[i][0] == L[0][0]:
    w_1.append(L[i][1])
  elif L[i][0] == L[0][0]+1:
    w_2.append(L[i][1])
  elif L[i][0] == L[0][0]+2:
    w_3.append(L[i][1])
  else:
    w_4.append(L[i][1])
w_1.sort()
w_2.sort()
w_3.sort()
w_4.sort()
w_1.reverse()
w_2.reverse()
w_3.reverse()
w_4.reverse()
for i in range(1,len(w_1)):
  w_1[i] = w_1[i-1]+w_1[i]
for i in range(1,len(w_2)):
  w_2[i] = w_2[i-1]+w_2[i]
for i in range(1,len(w_3)):
  w_3[i] = w_3[i-1]+w_3[i]
for i in range(1,len(w_4)):
  w_4[i] = w_4[i-1]+w_4[i]
w_1.append(0)
w_2.append(0)
w_3.append(0)
w_4.append(0)
for j in range(len(w_1)):
  for k in range(len(w_2)):
    for l in range(len(w_3)):
      for m in range(len(w_4)):
        if j*L[0][0]+k*(L[0][0]+1)+l*(L[0][0]+2)+m*(L[0][0]+3) > W:
          continue
        else:
          if w_1[j-1]+w_2[k-1]+w_3[l-1]+w_4[m-1] >= Vmax:
            Vmax = w_1[j-1]+w_2[k-1]+w_3[l-1]+w_4[m-1]
print(Vmax)

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:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w],v_cur+v)

print(max(dp.values()))

Solution (Python):
n,max_w = map(int,input().split())
w1=[]
w2=[]
w3=[]
w4=[]
v1=[]
v2=[]
v3=[]
v4=[]

w_1,v_1 = map(int,input().split())
w1.append(w_1)
v1.append(v_1)

for i in range(1,n):
  tmp_w,tmp_v = map(int,input().split())
  if tmp_w == w_1:
    w1.append(tmp_w)
    v1.append(tmp_v)
  elif tmp_w == w_1+1:
    w2.append(tmp_w)
    v2.append(tmp_v)
  elif tmp_w == w_1+2:
    w3.append(tmp_w)
    v3.append(tmp_v)
  elif tmp_w == w_1+3:
    w4.append(tmp_w)
    v4.append(tmp_v)
  

count1 = len(w1)
count2 = len(w2)
count3 = len(w3)
count4 = len(w4)

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

ruiseki_v1 = [0]*count1
ruiseki_v2 = [0]*count2
ruiseki_v3 = [0]*count3
ruiseki_v4 = [0]*count4

if v1:
  ruiseki_v1[0]=v1[0]
  for i in range(count1-1):
    ruiseki_v1[i+1]=ruiseki_v1[i]+v1[i+1]

if v2:
  ruiseki_v2[0]=v2[0]
  for i in range(count2-1):
    ruiseki_v2[i+1]=ruiseki_v2[i]+v2[i+1]

if v3:
  ruiseki_v3[0]=v3[0]
  for i in range(count3-1):
    ruiseki_v3[i+1]=ruiseki_v3[i]+v3[i+1]

if v4:
  ruiseki_v4[0]=v4[0]
  for i in range(count4-1):
    ruiseki_v4[i+1]=ruiseki_v4[i]+v4[i+1]

ruiseki_v1.insert(0,0)
ruiseki_v2.insert(0,0)
ruiseki_v3.insert(0,0)
ruiseki_v4.insert(0,0)

ans = 0 
for i in range(count1+1):
  for j in range(count2+1):
    for k in range(count3+1):
      for l in range(count4+1):
        if i*w_1 + j*(w_1+1) + k*(w_1+2) +l*(w_1+3) <= max_w:
          ans = max(ans,ruiseki_v1[i]+ruiseki_v2[j]+ruiseki_v3[k]+ruiseki_v4[l])
print(ans)

Solution (Python):
import sys
from collections import namedtuple


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


def next_int() -> int:
    return int(next_str())


item = namedtuple("itm", ("w", "v"))
n, W = map(int, input().split())
items = [item(next_int(), next_int()) for i in range(n)]
dic = dict()


def rec_dp(i: int, w: int) -> int:
    if (i, w) in dic:
        return dic[(i, w)]

    result = 0
    if i == n:
        pass
    elif w - items[i].w < 0:
        result = rec_dp(i + 1, w)
    else:
        result = max(
            rec_dp(i + 1, w),
            rec_dp(i + 1, w - items[i].w) + items[i].v
        )
    dic[(i, w)] = result
    return result


def main() -> None:
    print(rec_dp(0, W))


if __name__ == "__main__":
    main()

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

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

for i in d.keys():
    d[i].sort(reverse=True)
    *d[i],=accumulate([0]+d[i])

ans=0
i,j,k,l=d.keys()
for ai,bi in enumerate(d[i]):
    for aj,bj in enumerate(d[j]):
        for ak,bk in enumerate(d[k]):
            for al,bl in enumerate(d[l]):
                if i*ai+j*aj+k*ak+l*al<=W:
                    ans=max(ans,bi+bj+bk+bl)

print(ans)

Solution (Python):
def func(n, W, w):  
    _max = 0
    weights = [[] for _ in range(4)]
    for i in range(n):
        weights[w[i][0]-w[0][0]].append(w[i][1])
    for i in range(len(weights)):
        weights[i].sort()
        weights[i].append(0)
        weights[i].reverse()
        for j in range(1, len(weights[i])):
            weights[i][j] += weights[i][j-1]
    
    for i in range(len(weights[0])):
        
        for j in range(len(weights[1])):
            
            for k in range(len(weights[2])):
                for l in range(len(weights[3])):
                    
                    if w[0][0]*i\
                            + (w[0][0]+1)*j\
                            + (w[0][0]+2)*k\
                            + (w[0][0]+3)*l <= W:
                        
                        
                        _max = max(_max, weights[0][i]+weights[1][j]+weights[2][k]+weights[3][l])
    return _max


n, W = [int(i) for i in input().split()]
w = [[0, 0] for _ in range(n)]
for i in range(n):
    w[i] = [int(i) for i in input().split()]
print(func(n, W, w))
"""

print("11 vs " + str(func(4, 6, [[2, 1], [3, 4], [4, 10], [3, 4]])))
print("13 vs " + str(func(4, 6, [[2, 1], [3, 7], [4, 10], [3, 6]])))
print("400 vs " + str(func(4, 10, [[1, 100], [1, 100], [1, 100], [1, 100]])))
print("0 vs " + str(func(4, 1, [[10, 100], [10, 100], [10, 100], [10, 100]])))
"""

Solution (Python):
def solve(N, W, WVs):
    Ws = {}
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in Ws.items():
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        if w1 > W:
            break
        v1 = sum(Ws[wkeys[0]][:n1])
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                if w1 + w2 > W:
                    break
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    if w1 + w2 + w3 > W:
                        break
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        if w1 + w2 + w3 + w4 > W:
                            break
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    m = max(m, v1 + v2 + v3 + v4)

    return m

if __name__ == "__main__":
    N, W = map(int, input().split(" "))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, W, WVs))

Solution (Python):
from operator import itemgetter
import bisect
from itertools import accumulate
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
WV.sort(key=itemgetter(0, 1))
w, v = zip(*WV)
w0 = w[0]
w1 = w0 + 1
w2 = w1 + 1
w3 = w2 + 1
i0 = bisect.bisect_left(w, w0)
i1 = bisect.bisect_left(w, w1)
i2 = bisect.bisect_left(w, w2)
i3 = bisect.bisect_left(w, w3)
v0 = sorted(v[i0:i1], reverse=True)
v1 = sorted(v[i1:i2], reverse=True)
v2 = sorted(v[i2:i3], reverse=True)
v3 = sorted(v[i3:], reverse=True)
a0 = list(accumulate(v0)) + [0]
a1 = list(accumulate(v1)) + [0]
a2 = list(accumulate(v2)) + [0]
a3 = list(accumulate(v3)) + [0]
n0 = 1 + len(v0)
n1 = 1 + len(v1)
n2 = 1 + len(v2)
n3 = 1 + len(v3)

ans = 0
for i0 in range(n0):
    for i1 in range(n1):
        for i2 in range(n2):
            for i3 in range(n3):
                if i0*w0 + i1*w1 + i2*w2 + i3*w3 <= W:
                    ans = max(ans, a0[i0-1]+a1[i1-1]+a2[i2-1]+a3[i3-1])
print(ans)

Solution (Python):
from operator import itemgetter
import bisect
from itertools import accumulate
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
WV.sort(key=itemgetter(0, 1))
w, v = zip(*WV)
w0 = w[0]
w1 = w0 + 1
w2 = w1 + 1
w3 = w2 + 1
i0 = bisect.bisect_left(w, w0)
i1 = bisect.bisect_left(w, w1)
i2 = bisect.bisect_left(w, w2)
i3 = bisect.bisect_left(w, w3)
v0 = sorted(v[i0:i1], reverse=True)
v1 = sorted(v[i1:i2], reverse=True)
v2 = sorted(v[i2:i3], reverse=True)
v3 = sorted(v[i3:], reverse=True)
a0 = list(accumulate(v0)) + [0]
a1 = list(accumulate(v1)) + [0]
a2 = list(accumulate(v2)) + [0]
a3 = list(accumulate(v3)) + [0]
n0 = 1 + len(v0)
n1 = 1 + len(v1)
n2 = 1 + len(v2)
n3 = 1 + len(v3)

ans = 0
for i0 in range(n0):
    for i1 in range(n1):
        for i2 in range(n2):
            for i3 in range(n3):
                if i0*w0 + i1*w1 + i2*w2 + i3*w3 <= W:
                    ans = max(ans, a0[i0-1]+a1[i1-1]+a2[i2-1]+a3[i3-1])
print(ans)

Solution (Python):


"""
参考：https://atcoder.jp/contests/abc060/submissions/3958560
・前から普通にDPもdictでやってみる。
"""

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

from collections import defaultdict

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


dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for k, v in dp[i].items():
        
        if k + wN[i] <= W:
            dp[i+1][k+wN[i]] = max(dp[i][k] + vN[i], dp[i+1][k+wN[i]])
        
        dp[i+1][k] = max(dp[i][k], dp[i+1][k])


print(max(dp[N].values()))

Solution (Python):


"""
参考：https://img.atcoder.jp/arc073/editorial.pdf
　　　https://ei1333.hateblo.jp/entry/2017/05/01/004235
　　　https://atcoder.jp/contests/abc060/submissions/3782609
・公式解
・累積和あり
"""

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

from collections import defaultdict

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


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


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

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