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())
lst = [[0]*(n+1) for _ in range(4)]
for i in range(n):
    w,v = map(int,input().split())
    if i == 0: x = w
    lst[w-x].append(v)
for i in range(4):
    lst[i].sort(reverse=True)
    for j in range(n): lst[i][j+1] += lst[i][j]
ans = 0
for a in range(n+1):
    for b in range(n+1-a):
        for c in range(n+1-a-b):
            if x*a+(x+1)*b+(x+2)*c > W: continue
            d = max((W-x*a-(x+1)*b-(x+2)*c)//(x+3),0)
            sumv = 0
            for i,j in enumerate((a,b,c,d)):
                if j == 0: continue
                sumv += lst[i][j-1]
            ans = max(sumv,ans)
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())
x = w[0]
for i in range(n): w[i] -= x
dp = [[[0]*(4*n+1) for _ in range(n+1)] for _ in range(n+1)]

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

"""
for i in range(n+1):
    print(i,"///////////////////////////////////////////////")
    for j in range(n+1):
        print(dp[i][j])
"""
print(max(max(dp[n][j]) for j in range(n+1)))

Solution (Python):
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
from collections import Counter
w0=wv[0][0]
d={w0:[0],w0+1:[0],w0+2:[0],w0+3:[0],}
for w,v in wv:
  d[w].append(v)
for i in range(4):
  d[w0+i].sort(reverse=True)
sd={}
for i in range(4):
  tmp=0
  sd[w0+i]=[0]
  for v in d[w0+i]:
    tmp+=v
    sd[w0+i].append(tmp)
ans=0
for i in range(len(d[w0])):
  for j in range(len(d[w0+1])):
    for k in range(len(d[w0+2])):
      for l in range(len(d[w0+3])):
        if w0*i+(w0+1)*j+(w0+2)*k+(w0+3)*l<=W:
          ans=max(ans,sd[w0][i]+sd[w0+1][j]+sd[w0+2][k]+sd[w0+3][l])
print(ans)

Solution (Python):
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1

for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)

dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][min(W-i*w0,400)])
print(ans)

Solution (Python):
def main():
    n, w = map(int, input().split())
    w1, v1 = map(int, input().split())
    values = [[] for _ in range(4)]
    values[0].append(v1)
    for _ in range(n - 1):
        wi, vi = map(int, input().split())
        values[wi - w1].append(vi)
    for i in range(4):
        values[i].sort(reverse=True)
    prefix = [[0] for _ in range(4)]
    for i in range(4):
        for j in range(len(values[i])):
            prefix[i].append(prefix[i][-1] + values[i][j])
    max_ans = 0
    tot_val = [0] * 4
    tot_weights = [0] * 4
    for i in range(min(len(values[0]), w // w1) + 1):
        tot_val[0] = prefix[0][i]
        tot_weights[0] = w1 * i
        for j in range(min(len(values[1]), w // (w1 + 1)) + 1):
            tot_val[1] = tot_val[0] + prefix[1][j]
            tot_weights[1] = tot_weights[0] + (w1 + 1) * j
            if tot_weights[1] > w:
                break
            for k in range(min(len(values[2]), w // (w1 + 2)) + 1):
                tot_val[2] = tot_val[1] + prefix[2][k]
                tot_weights[2] = tot_weights[1] + k * (w1 + 2)
                if tot_weights[2] > w:
                    break
                diff = w - tot_weights[2]
                min_select = min(diff // (w1 + 3), len(values[3]))
                tot_val[3] = tot_val[2] + prefix[3][min_select]
                tot_weights[3] = tot_weights[2] + min_select * (w1 + 3)
                max_ans = max(max_ans, tot_val[3])
    print(max_ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,w=map(int,input().split())
knap=[[] for i in range(4)]
w0,v=map(int,input().split())
knap[0].append(v)
for i in range(n-1):
    W,v=map(int,input().split())
    knap[W-w0].append(v)
for i in range(4):
    knap[i].sort(reverse=1)
    knap[i]=[0]+knap[i]
for i in range(4):
    for j in range(1,len(knap[i])):
        knap[i][j]+=knap[i][j-1]
ans=0
for a in range(len(knap[0])):
    for b in range(len(knap[1])):
        for c in range(len(knap[2])):
            for d in range(len(knap[3])):
                if w0*a+(w0+1)*b+(w0+2)*c+(w0+3)*d<=w:
                    ans=max(ans,knap[0][a]+knap[1][b]+knap[2][c]+knap[3][d])
print(ans)

Solution (Python):
def main():
    N, W = map(int, input().split())
    l = []
    w, v = map(int, input().split())
    ww = w
    dp = [[[0] * (3*N) for _ in range(N+1) ]for _ in range(N)]
    dp[0][1][0] = v
    l.append((0, v))
    for _ in range(N-1):
        w, v = map(int, input().split())
        l.append((w-ww, v))
    if W < ww:
        return 0
    for i in range(1, N):
        w, v = l[i]
        for j in range(1, N+1):
            for k in range(w):
                dp[i][j][k] = dp[i-1][j][k]
            for k in range(w, 3*N):
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
    r = 0
    for i in range(N+1):
        wt = W - i * ww
        if wt < 0:
            break
        r = max(r, max(dp[-1][i][:wt+1]))
    return r
print(main())

Solution (Python):
def main():
    N, W = map(int, input().split())
    WV = [tuple(map(int, input().split())) for _ in range(N)]
    cur = {0: 0}
    for w, v in WV:
        keys = sorted(cur.keys(), reverse=True)
        for k in keys:
            if k + w > W:
                continue
            cur[k + w] = max(cur[k] + v, cur.get(k + w, 0))
    return max(cur.values())

print(main())

Solution (Python):
from itertools import accumulate

N, W = map(int, input().split())
wv = {}
w1 = 0
for i in range(N):
  w, v = map(int, input().split())
  if i == 0:
    w1 = w
  if w in wv:
    wv[w].append(v)
  else:
    wv[w] = [v]

for w in wv:
  wv[w].sort(reverse=True)
  wv[w] = [0] + list(accumulate(wv[w]))

w2 = w1+1; w3 = w1+2; w4 = w1+3
for w in [w1, w1+1, w1+2, w1+3]:
  if w not in wv:
    wv[w] = [0]

ans = 0
for n1 in range(len(wv[w1])):
  for n2 in range(len(wv[w2])):
    for n3 in range(len(wv[w3])):
      for n4 in range(len(wv[w4])):
        w = w1*n1 + w2*n2 + w3*n3 + w4*n4
        if w <= W:
          ans = max(ans, wv[w1][n1]+wv[w2][n2]+wv[w3][n3]+wv[w4][n4])

print(ans)

Solution (Python):
from itertools import accumulate

N, W = map(int, input().split())
wv = {}
w1 = 0
for i in range(N):
  w, v = map(int, input().split())
  if i == 0:
    w1 = w
  if w in wv:
    wv[w].append(v)
  else:
    wv[w] = [v]

for w in wv:
  wv[w].sort(reverse=True)
  wv[w] = [0] + list(accumulate(wv[w]))

w2 = w1+1; w3 = w1+2; w4 = w1+3
for w in [w1, w1+1, w1+2, w1+3]:
  if w not in wv:
    wv[w] = [0]

ans = 0
for n1 in range(len(wv[w1])):
  for n2 in range(len(wv[w2])):
    for n3 in range(len(wv[w3])):
      for n4 in range(len(wv[w4])):
        w = w1*n1 + w2*n2 + w3*n3 + w4*n4
        if w <= W:
          ans = max(ans, wv[w1][n1]+wv[w2][n2]+wv[w3][n3]+wv[w4][n4])

print(ans)

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

w_to_idx = {0:0}
idx_to_w = {0:0}
idx_W = 0
def calc():
  global w_to_idx, idx_to_w, idx_W
  idx = 1
  w_max = 0
  for i in range(1, N+1):
    w = w1*i
    for j in range(3*i + 1):
      ww = w + j
      if ww in w_to_idx:
        continue
      w_to_idx[ww] = idx
      idx_to_w[idx] = ww
      if w_max < ww <= W:
        w_max = ww
        idx_W = idx
      idx += 1

calc()
n = len(w_to_idx)
dp = [[0]*n for i in range(N+1)]
for i, (w, v) in enumerate(wv, 1):
  for j in range(n):
    dp[i][j] = dp[i-1][j]
    ww = idx_to_w[j]
    if ww >= w and ww-w in w_to_idx:
      jj = w_to_idx[ww - w]
      dp[i][j] = max(dp[i][j], dp[i-1][jj] + v)

print(max(dp[-1][:idx_W+1]))

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

items = [[] for _ in range(4)]
w1, v = [int(_) for _ in input().split()]
items[0].append(v)

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

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

S = []
for i in range(4):
    l = len(items[i])
    s = [0] * (l + 1)
    for j in range(l):
        s[j + 1] = items[i][j] + s[j]
    S.append(s)

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

Solution (Python):
n, w = map(int, input().split())
ws, vs = [], []
for i in range(n):
  wi, vi = map(int, input().split())
  ws.append(wi)
  vs.append(vi)
dp = [[[0] * (3 * i + 1) for i in range(n + 1)] for j in range(n + 1)]
for i in range(n):
  for j in range(n + 1):
    for k in range(3 * j + 1):
      dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
      if j < n:
        dp[i + 1][j + 1][k + ws[i] - ws[0]] = max(dp[i + 1][j + 1][k + ws[i] - ws[0]],
                                                  dp[i][j][k] + vs[i])
ans = 0
for i in range(n + 1):
  for j in range(3 * i + 1):
    if ws[0] * i + j <= w:
      ans = max(ans, dp[n][i][j])
print(ans)

Solution (Python):
from collections import defaultdict


def main():
    N, W = list(map(int, input().split(' ')))
    items, cumsums = defaultdict(list), defaultdict(list)
    w_0 = 0
    for i in range(N):
        w, v = list(map(int, input().split(' ')))
        if i == 0:
            w_0 = w
        items[w].append(v)
    for w in items.keys():
        items[w].sort(reverse=True)
        cumsum_w, cumsum_v = 0, 0
        for v in items[w]:
            cumsum_w += w
            cumsum_v += v
            
            cumsums[w - w_0].append((cumsum_w, cumsum_v))

    def dfs(cur, rest_w):
        if cur == 0:
            max_v = 0
            for cumsum_w, cumsum_v in cumsums[cur]:
                if cumsum_w <= rest_w:
                    max_v = cumsum_v
            return max_v
        else:
            ret = dfs(cur - 1, rest_w)
            for cumsum_w, cumsum_v in cumsums[cur]:
                if rest_w >= cumsum_w:
                    ret = max([ret, cumsum_v + dfs(cur - 1, rest_w - cumsum_w)])
            return ret

    print(dfs(3, W))


if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
data = tuple(tuple(map(int, input().split())) for _ in range(N))
d = {0: 0}
for n in range(N):
    weight, value = data[n]
    for w, now in d.copy().items():
        if w + weight <= W:
            d[w + weight] = max(d.get(w + weight, 0), now + value)
print(max(d.values()))

Solution (Python):
N, W = map(int, input().split())
data = tuple(tuple(map(int, input().split())) for _ in range(N))
table = [dict() for _ in range(N + 1)]
table[0][0] = 0
for n in range(N):
    weight, value = data[n]
    for w, now in table[n].items():
        table[n + 1][w] = max(table[n + 1].get(w, 0), now)
        if w + weight <= W:
            table[n + 1][w + weight] = max(table[n + 1].get(w + weight, 0), now + value)
print(max(table[N].values()))

Solution (Python):
from itertools import product

N, W = map(int,input().split())
L = [[] for _ in range(4)]
w, v = map(int,input().split())
L[0].append(v)
for _ in range(N-1):
    tmp_w, tmp_v = map(int,input().split())
    L[tmp_w - w].append(tmp_v)

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

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

ans = 0

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

print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True




def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)






def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



N, W = map(int, input().split())
v = [[] for i in range(4)]
w1 = 0
for i in range(N):
    a, b = map(int, input().split())
    if i == 0:
        w1 = a
    v[a - w1].append(b)
for i in range(4):
    v[i].sort(reverse=True)

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

Solution (Python):


import sys
























from itertools import accumulate             





def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    n, w = mi()
    L = [lmi() for _ in range(n)]
    w1 = L[0][0]
    if n * (w1 + 3) <= w:
        print(sum(map(lambda x: x[1], L)))
    elif n * w <= 10**6:
        
        dp = [0 for _ in range(w+1)]
        for i in range(n):
            weight, value = L[i]
            for j in range(w, 0, -1):
                if j - weight >= 0:
                    dp[j] = max(dp[j], dp[j - weight] + value)
        print(dp[w])
    else:
        group_by_weight = [[] for _ in range(4)]
        for weight, value in L:
            group_by_weight[weight - w1].append(value)
        w1_0 = sorted(group_by_weight[0], reverse=True)
        w1_1 = sorted(group_by_weight[1], reverse=True)
        w1_2 = sorted(group_by_weight[2], reverse=True)
        w1_3 = sorted(group_by_weight[3], reverse=True)
        accum_0, accum_1, accum_2, accum_3 = map(lambda x: [0] + list(accumulate(x)), [w1_0, w1_1, w1_2, w1_3])
        ans = -1
        for i in range(len(w1_0)+1):
            for j in range(len(w1_1)+1):
                for k in range(len(w1_2)+1):
                    for l in range(len(w1_3)+1):
                        if (i+j+k+l)*w1 + j + 2*k + 3*l <= w:
                            ans = max(ans, accum_0[i] + accum_1[j] + accum_2[k] + accum_3[l])
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,W=map(int,input().split())
    w,v=[0]*N,[0]*N
    for i in range(N):
        w[i],v[i]=map(int,input().split())
    if w[0]>3*N:
        w0=w[0]
        W=min(W//w0*(3*N+1)+min(W%w0,3*N),(3*N+4)*N)
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N+1
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            if j-w[i]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

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

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

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

for i in stuff:
    i.sort(reverse=True)

ans = 0

for a in range(len(stuff[0])+1):
    for b in range(len(stuff[1])+1):
        for c in range(len(stuff[2])+1):
            for d in range(len(stuff[3])+1):

                if a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3) <= W:
                    ans = max(ans,sum(stuff[0][:a])+sum(stuff[1][:b])+sum(stuff[2][:c])+sum(stuff[3][:d]))

print(ans)

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

memo = {}

def  nap(i, j):
    if i == N:
        return 0

    if (i, j) in memo:
        return memo[i, j]
    elif w_v[i][0] > j:
        temp = nap(i+1, j)
    else:
        temp = max(nap(i+1, j), nap(i+1, j-w_v[i][0]) + w_v[i][1])
    memo[i, j] = temp

    return memo[i, j]

print(nap(0, W))

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

dp = [[[0]*(3*n+1) for i in range(n+1)] for j in range(n+1)]
s = l[0][0]

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

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

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

wv.sort(key=lambda x:(x[0],-x[1]))



min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - min_v] +=1
        




t_num3 = [0]
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]+i][1]
    t_num3.append(tmp)




t_ans = 0
t_num0 = 0
ans = 0


for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3)
            if ima_w > w:
                break
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3])]
        
            ans = max(t_ans,ans)

print(ans)

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

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

w1=wvlist[0][0]

w2vlist=[]
for i in range(N):
  w,v=wvlist[i]
  w2vlist.append((w,w-w1,v))


dp=[[[0]*(3*N+1) for _ in range(N+1)] for _ in range(N+1)]


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

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

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

dp = [[[0]*(3*n+1) for _ in range(n)] for _ in range(n)]

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*(j+1)+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

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

dp = [[[0]*(3*n+1) for _ in range(n)] for _ in range(n)]

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*n+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

Solution (Python):
from collections import defaultdict
N,W=map(int,input().split())

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


wv_sorted=sorted(wvdic.items())


wvslist=[]
for i in range(len(wv_sorted)):
  slist=[0]
  vlist=sorted(wv_sorted[i][1],reverse=True)
  for v in vlist:
    slist.append(slist[-1]+v)
  wvslist.append((wv_sorted[i][0],slist))
if len(wvslist)<4:
  for _ in range(4-len(wvslist)):
    wvslist.append((-1,[0]))


max_answer=0
for w1 in range(len(wvslist[0][1])):
  ww1=wvslist[0][0]*w1
  v1=wvslist[0][1][w1]
  for w2 in range(len(wvslist[1][1])):
    ww2=wvslist[1][0]*w2
    v2=wvslist[1][1][w2]
    for w3 in range(len(wvslist[2][1])):
      ww3=wvslist[2][0]*w3
      v3=wvslist[2][1][w3]
      for w4 in range(len(wvslist[3][1])):        
        ww4=wvslist[3][0]*w4
        v4=wvslist[3][1][w4]
        ww_total=ww1+ww2+ww3+ww4
        
        if ww_total<=W:
          vtotal=v1+v2+v3+v4
          max_answer=max(max_answer,vtotal)
          
print(max_answer)

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

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

w1=wvlist[0][0]

w2vlist=[]
for i in range(N):
  w,v=wvlist[i]
  w2vlist.append((w,w-w1,v))


dp=[[[0 for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]


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

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

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




dp_dict = {0: {0:0}} 

'''
for i,pack in enumerate(pack_list):
    for value,weight in enumerate(dp[i]):
        dp[i+1][value] = min(dp[i][value],dp[i+1][value])
        dp[i+1][value+pack[1]] = min(dp[i+1][value+pack[1]],dp[i][value]+pack[0])

for i,num in enumerate(dp[-1][::-1]):
    if num <= w:
        print(10**7-i)'''

for i,pack in enumerate(pack_list):
    i += 1
    if i not in dp_dict:
        dp_dict[i] = {}
    for weight,v in dp_dict[i-1].items():
        if weight not in dp_dict[i]:
            dp_dict[i][weight] = v
        else:
            dp_dict[i][weight] = max(dp_dict[i][weight],v)
        if weight+pack[0] <= w:
            if weight+pack[0] not in dp_dict[i]:
                dp_dict[i][weight+pack[0]] = v+pack[1]
            else:
                dp_dict[i][weight+pack[0]] = max(dp_dict[i][weight+pack[0]],v+pack[1])

target = dp_dict[n]
max_num = 0

for k,v in target.items():
    if k <= w:
        max_num = max(max_num,v)

print(max_num)

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

w0 = X[0][0]
ctr = [[] for _ in range(4)]
for w, v in X:
    ctr[w - w0].append(v)

for n in range(4):
    values = sorted(ctr[n], reverse=True)
    s = [0] * (len(values) + 1)
    for i in range(len(values)):
        s[i + 1] = s[i] + values[i]
    ctr[n] = s

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

print(ans)

Solution (Python):
from itertools import accumulate
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)

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




ans=0
for a in range(len(w1)):
    for b in range(len(w2)):
        for c in range(len(w3)):
            for d in range(len(w4)):
                
                wei=w*a+(w+1)*b+(w+2)*c+(w+3)*d
                val=w1[a]+w2[b]+w3[c]+w4[d]
                
                if wei<=W:
                    ans=max(val,ans)

print(ans)

Solution (Python):


def submit():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    
    if items[0][0] > w:
        print(0) 
        return

    if sum([e[0] for e in items]) <=  w:
        print(sum([e[1] for e in items])) 
        return

    
    
    base_weight = items[0][0]
    
    
    
    
    
    
    
    dp = [[[0 for _ in range(3 * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        rw = items[i - 1][0] - base_weight
        v = items[i - 1][1]
        for j in range(i + 1):
            for k in range(3 * n + 1):
                if j * base_weight + k <= w:
                    if j - 1 >= 0 and k - rw >= 0:
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - rw] + v)
                    else:
                        dp[i][j][k] = dp[i - 1][j][k]
                else:
                    break

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

submit()

Solution (Python):
import numpy as np
from itertools import product
from collections import  defaultdict as dd
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wi = wv[0][0]
vi = wv[0][1]
dic = dd(list)
dic_cumsum = dd(list)
for w,v in wv:
    dic[w].append(v)

for k,v in dic.items():
    tmp = sorted(v, reverse=True)
    dic_cumsum[k] = [0] + list(np.zeros((N + 1), dtype=np.int64))
    dic_cumsum[k][1:] = list(np.cumsum(tmp, dtype=np.int64))
for i in range(1,4):
    if wi+i not in dic_cumsum.keys():
        dic_cumsum[wi+i] = [0]
        
n = [len(dic_cumsum[wi]), len(dic_cumsum[wi+1]), len(dic_cumsum[wi+2]), len(dic_cumsum[wi+3])]
m = [list(range(val)) for val in n]
res = 0

for ls in product(m[0], m[1], m[2]):
    if sum(ls)*wi > W:
        continue
    tmp_value = 0
    tmp_weight = 0
    for i,k in enumerate(ls):
        tmp_value += dic_cumsum[wi + i][k]
        tmp_weight += k*(wi+i)
    if tmp_weight > W:
        continue
    
    max_m3 = (W - tmp_weight) // (wi+3)
    m3 = min(max_m3, n[3]-1)
    tmp_value += dic_cumsum[wi+3][m3]
    if tmp_value > res:
        res = tmp_value
print(res)