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):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












n,w= list(map(int, input().split()))
item = [[] for i in range(4)]
ww = 0
for i in range(n):
    temp = list(map(int, input().split()))
    if(i==0):
        ww = temp[0]
    item[temp[0]-ww].append(temp[1])
    
for i in range(4):
    item[i].sort()
    item[i].reverse()


ans = 0

sums = [[0],[0],[0],[0]]

for i in range(4):
    for j in rl(item[i]):
        sums[i].append(sums[i][-1] + item[i][j])



for i1 in range(len(item[0])+1):
    for i2 in range(len(item[1])+1):
        for i3 in range(len(item[2])+1):
            for i4 in range(len(item[3])+1):
                wei = (i1+i2+i3+i4)*ww + i2 + i3*2 + i4*3
                if(wei<=w):
                    val = sums[0][i1] + sums[1][i2] + sums[2][i3] + sums[3][i4]
                    ans = max(ans,val)

print(ans)

Solution (Python):

def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)

Solution (Python):
import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    cumsum = dict()
    L = defaultdict(int)
    for i in range(4):
        w = w1 + i
        d[w].sort(reverse=True)
        c = np.cumsum(d[w])
        cumsum[w] = c
        L[i] = len(d[w])

    ans = 0
    for i in range(L[0] + 1):
        if i != 0:
            v1 = cumsum[w1][i - 1]
        else:
            v1 = 0
        for j in range(L[1] + 1):
            if j != 0:
                v2 = v1 + cumsum[w1 + 1][j - 1]
            else:
                v2 = v1
            for k in range(L[2] + 1):
                if k != 0:
                    v3 = v2 + cumsum[w1 + 2][k - 1]
                else:
                    v3 = v2
                for l in range(L[3] + 1):
                    w = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                    if w > W:
                        continue

                    if l != 0:
                        v4 = v3 + cumsum[w1 + 3][l - 1]
                    else:
                        v4 = v3

                    if v4 > ans:
                        ans = v4

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import groupby, product
    base_w = w[0]
    v_list = [[] for _ in range(4)]
    for ww, vv in zip(w, v):
        v_list[ww-base_w].append(vv)
    v_list = [sorted(vv, reverse=True) for vv in v_list]
    acc_v = [[0] for _ in range(4)]
    for i, vv in enumerate(v_list):
        for vvv in vv:
            acc_v[i].append(acc_v[i][-1] + vvv)
    ans = 0
    for i, j, k, l in product(*[range(len(a)) for a in acc_v]):
        if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) > W:
            continue
        ans = max(ans, acc_v[0][i] + acc_v[1][j] + acc_v[2][k] + acc_v[3][l])
    return ans


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    W = int(next(tokens))  
    w = [int()] * (N)  
    v = [int()] * (N)  
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import sys

N, W = map(int, sys.stdin.readline().strip().split())

weights = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().strip().split())
    weights.append((w, v))

MAX_WEIGHTS = 4 * 101

dp = [[[-1 for _ in range(MAX_WEIGHTS)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

ans = 0
BASE = weights[0][0]
for i in range(N):
    for j in range(i+1):
        for k in range(MAX_WEIGHTS):
            if dp[i][j][k] < 0:
                continue
            w, v = weights[i]
            w -= BASE
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            ans = max(ans, dp[i+1][j][k])
            if k + w + (j+1) * BASE <= W and k + w < MAX_WEIGHTS:
                dp[i+1][j+1][k+w] = dp[i][j][k] + v
                ans = max(ans, dp[i+1][j+1][k+w])

print(ans)

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

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

wi,vi=map(int,input().split())
w1=wi
ws[w1-wi].append(vi)

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

for i in range(4):
    ws[i]=sorted(ws[i])[::-1]

ans=0

for i in range(-1,len(ws[0])):
    sum_vi=0
    wi=0

    if(i!=-1):
        sum_vi=sum(ws[0][:i+1])
        wi=w1*(i+1)
    if(wi>w):

        break

    for j in range(-1,len(ws[1])):
        sum_vj=sum_vi
        wj=wi

        if(j!=-1):
            sum_vj=sum_vi+sum(ws[1][:j+1])
            wj=wi+(w1+1)*(j+1)
        if(wj>w):

            break

        for k in range(-1,len(ws[2])):
            sum_vk=sum_vj
            wk=wj

            if(k!=-1):
                sum_vk=sum_vj+sum(ws[2][:k+1])
                wk=wj+(w1+2)*(k+1)
            if(wk>w):

                break

            w_rest=w-wk
            l=w_rest//(w1+3)
            sum_vl=sum_vk
            wl=wk

            if(l>len(ws[3])):
                sum_vl+=sum(ws[3])
                wl+=(w1+3)*len(ws[3])
            else:
                sum_vl+=sum(ws[3][:l])
                wl+=(w1+3)*l

            if(ans<sum_vl):

                ans=sum_vl
print(ans)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

N,W = MI()
WV = LI(N)

ls_w = mycol(WV,0)
ls_w = list(set(ls_w))
ls_w.sort()
if len(ls_w)==3:
    ls_w = [0] + ls_w
elif len(ls_w)==2:
    ls_w = [0,0] + ls_w
elif len(ls_w)==1:
    ls_w = [0,0,0] + ls_w
else:
    pass


a = []
b = []
c = []
d = []
for i in range(N):
    w = WV[i][0]
    v = WV[i][1]
    ind = ls_w.index(w)
    if ind==0:
        a.append(v)
    elif ind==1:
        b.append(v)
    elif ind==2:
        c.append(v)
    elif ind==3:
        d.append(v)
    else:
        print("E")
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
d.sort(reverse=True)







M = -1*INF

for i in range(len(a)+1):
    for j in range(len(b)+1):
        for k in range(len(c)+1):
            for l in range(len(d)+1):
                w = i*ls_w[0] + j*ls_w[1] + k*ls_w[2] + l*ls_w[3]
                if w>W:
                    pass
                else:
                    v = sum(a[:i]) + sum(b[:j]) + sum(c[:k]) + sum(d[:l])
                    M = max(M,v)
print(M)

Solution (Python):
import collections
N, W = map(int, input().split())
wv = collections.defaultdict(list)
w = 0
for i in range(N):
    a, b = map(int, input().split())
    wv[a].append(b)
    if i == 0:
        w = a
s = [[0]*(len(wv[w+i])+1) for i in range(4)]

for i in range(4):
    wv[w + i].sort(reverse=True)
    for j, x in enumerate(wv[w + i]):
        s[i][j+1] = s[i][j] + x
ans = 0
L = len(wv[w+3])
for i in range(min(len(wv[w]), N)+1):
    tmp1 = s[0][i]
    weight1 = w * i
    if weight1 > W:
        break
    for j in range(min(len(wv[w+1])+1, N+1 - i)):

        tmp2 = tmp1 + s[1][j]
        weight2 = weight1 + (w+1)*j
        if weight2 > W:
            break
        for k in range(min(len(wv[w+2])+1, N+1 - i - j)):
            tmp3 = tmp2 + s[2][k]
            weight3 = weight2 + (w+2)*k
            if weight3 > W:
                break
            d = W - weight3

            ans = max(ans, tmp3 + s[3][min(L, d//(w+3))])
print(ans)

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

WV = [tuple(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
R = N * 3

dp = [[-10**18] * (R + 1) for _ in range(N + 1)]
dp[0][0] = 0

for w, v in WV:
    w -= W0
    for n in range(N)[::-1]:
        for i in range(R)[::-1]:
            if i + w <= R:
                dp[n + 1][i + w] = max(dp[n + 1][i + w], dp[n][i] + v)

ans = 0
for n in range(N + 1):
    for w in range(R + 1):
        if n * W0 + w <= W:
            ans = max(ans, dp[n][w])
print(ans)

Solution (Python):
N, W = map(int, input().split())
L = [[] for _ in range(4)]
wv = [tuple(map(int, input().split())) for _ in range(N)]
w0 = wv[0][0]

for w, v in wv:
    L[w-w0].append(v)

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

acc = [[0] for _ in range(4)]

for i in range(4):
    for j in range(len(L[i])):
        acc[i].append(acc[i][-1]+L[i][j])

ans = 0

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

print(ans)

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

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

w1,v1 = map(int,input().split())

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 w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
                    ans = max(ans,sum(stuff[0][:a])+sum(stuff[1][:b])+sum(stuff[2][:c])+sum(stuff[3][:d]))
        
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,W = LI()
    B = [[0,0]]+[LI() for _ in range(N)]

    k_min = max(1,W // (B[1][0] + 3))
    k_max = min(W // B[1][0],N)

    if B[1][0] <= 300: base = 0
    else: base = B[1][0] - 300
    for i in range(1,N+1): B[i][0] -= base

    ans = 0
    for k in range(k_min,k_max+1):
        w_sub = min(303 * k,W - k*base)
        dp = [[0] * (w_sub+1) for _ in range(N+1)]
        for i in range(1,N+1):
            for j in range(1,w_sub+1):
                if j - B[i][0] >= 0:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-B[i][0]] + B[i][1])
                else:
                    dp[i][j] = dp[i-1][j]
        ans = max(ans,dp[-1][-1])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    dp = collections.defaultdict(lambda: -1)
    dp[0] = 0
    for i in range(N):
        wi, vi = items[i]
        ndp = collections.defaultdict(lambda: -1)
        for ws, vs in dp.items():
            if ws + wi <= W:
                ndp[ws + wi] = max(ndp[ws + wi], vs + vi)
        for wt, vt in ndp.items():
            dp[wt] = max(dp[wt], vt)
    return max(dp.values())


if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    dp = collections.defaultdict(lambda: -1)
    dp[0] = 0
    for i in range(N):
        wi, vi = items[i]
        ndp = collections.defaultdict(lambda: -1)
        for ws, vs in dp.items():
            if ws + wi <= W:
                ndp[ws + wi] = max(ndp[ws + wi], vs + vi)
        for wt, vt in ndp.items():
            dp[wt] = max(dp[wt], vt)
    return max(dp.values())


if __name__ == "__main__":
    print(solve())

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


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


if __name__ == "__main__":
    main()

Solution (Python):





N,W = map(int,input().split())
items = [None] * N
items[0] = list(map(int,input().split()))
base = items[0][0]
items[0][0] = 0
for i in range(1,N):
  items[i] = list(map(int,input().split()))
  items[i][0] -= base


dp = [[-1 for i in range(N + 1)] for j in range(3 * N + 1)]

dp[0][0] = 0
for i in range(len(items)):
  w = items[i][0]
  v = items[i][1]
  for j in range(len(dp)-1,-1,-1):
    
    for k in range(len(dp[j])-1,-1,-1):
      
      if dp[j][k] != -1:
        if j + w < len(dp) and k * base + j <= W:
          if dp[j + w][k + 1] < dp[j][k] + v:
            dp[j + w][k + 1] = dp[j][k] + v
            
ans = 0
for i in range(len(dp)):
  for j in range(len(dp[i])):
    if i + j * base <= W and ans < dp[i][j]:
      ans = dp[i][j]
      
print(ans)

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

from collections import defaultdict
vals = defaultdict(list)
for tmp in wv:
    w,v=tmp
    vals[w-w1].append(v)

v1=sorted(vals[0],reverse=True)
v2=sorted(vals[1],reverse=True)
v3=sorted(vals[2],reverse=True)
v4=sorted(vals[3],reverse=True)

ans=-1
for num1 in range(len(v1)+1):
    for num2 in range(len(v2)+1):
        for num3 in range(len(v3)+1):
            for num4 in range(len(v4)+1):
                sumw = num1*w1 + num2*(w1+1) + num3*(w1+2) + num4*(w1+3)
                if sumw <=weight:
                    sm = sum(v1[:num1]) + sum(v2[:num2]) +  sum(v3[:num3]) +  sum(v4[:num4])
                    ans=max(ans,sm)
print(ans)

Solution (Python):
N, W = map(int, input().split(" "))
items = {i: [] for i in range(4)}
w1 = -1
for _ in range(N):
    w, v = map(int, input().split(" "))
    if w1 == -1:
        w1 = w
    items[w - w1].append(v)

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

ans = 0
for i in range(len(items[3])):
    if i * (w1 + 3) > W:
        break
    for j in range(len(items[2])):
        if i * (w1 + 3) + j * (w1 + 2) > W:
            break
        for k in range(len(items[1])):
            if i * (w1 + 3) + j * (w1 + 2) + k * (w1 + 1) > W:
                break
            w_three = (W - i * (w1 + 3) - j * (w1 + 2) - k * (w1 + 1)) // w1
            w_three = min(len(items[0]) - 1, w_three)
            ans = max(items[3][i] + items[2][j] + items[1][k] + items[0][w_three], ans)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in [0]*N]
w0 = A[0][0]
A = [(w-w0, v) for w, v in A]

dp = [[0]*(3*N) for _ in [0]*(N+1)]
ans = 0
sumw = 0
for k, (w, v) in enumerate(A):
    for i in range(k, -1, -1):
        for j in range(sumw, -1, -1):
            if 0 <= i < N and 0 <= j+w < 3*N and (i+1)*w0+j+w <= W:
                dp[i+1][j+w] = max(dp[i][j]+v, dp[i+1][j+w])
    sumw += w

for d in dp:
    ans = max(ans, *d)
print(ans)

Solution (Python):
def main():
    N, W = map(int, input().split())
    ctr = [0] * 4
    goods = [[] for _ in range(4)]

    w1, v1 = map(int, input().split())
    ctr[0] += 1
    goods[0].append(v1)

    for _ in range(N - 1):
        wi, vi = map(int, input().split())
        wi -= w1
        ctr[wi] += 1
        goods[wi].append(vi)

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

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    accs = [list(accumulate(goods_i)) for goods_i in goods]

    ans = -1
    for c0 in range(N + 1):
        if ctr[0] < c0: break
        if w1 * c0 > W: break

        v0 = accs[0][c0]
        for c1 in range(N - c0 + 1):
            if ctr[1] < c1: break
            if w1 * c0 + (w1 + 1) * c1 > W: break

            v1 = v0 + accs[1][c1]
            for c2 in range(N - c0 - c1 + 1):
                if ctr[2] < c2: break
                if w1 * c0 + (w1 + 1) * c1 + (w1 + 2) * c2 > W: break

                v2 = v1 + accs[2][c2]
                for c3 in range(N - c0 - c1 - c2 + 1):
                    if ctr[3] < c3: break
                    if w1 * c0 + (w1 + 1) * c1 + (w1 + 2) * c2 + (w1 + 3) * c3 > W: break
                    v3 = v2 + accs[3][c3]
                    ans = max(ans, v3)

    print(ans)


if __name__ == '__main__':
    main()

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


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


if __name__ == "__main__":
    main()

Solution (Python):
import copy

n, W = map(int, input().split())
product = [[0] for _ in range(4)]

w, v = map(int, input().split())
w_0 = w
product[0].append(v)
for i in range(n-1):
  w, v = map(int, input().split())
  product[w-w_0].append(v)

product[0].sort()
product[1].sort()
product[2].sort()
product[3].sort()

for i in range(len(product[0])-1):
  product[0][i+1] = product[0][i+1]+product[0][i]
for i in range(len(product[1])-1):
  product[1][i+1] = product[1][i+1]+product[1][i]
for i in range(len(product[2])-1):
  product[2][i+1] = product[2][i+1]+product[2][i]
for i in range(len(product[3])-1):
  product[3][i+1] = product[3][i+1]+product[3][i]

ans = 0
for a in range(len(product[0])):
  for b in range(len(product[1])):
    for c in range(len(product[2])):
      for d in range(len(product[3])):
        weight = w_0*(len(product[0])-a-1)+(w_0+1)*(len(product[1])-b-1)+(w_0+2)*(len(product[2])-c-1)+(w_0+3)*(len(product[3])-d-1)
        if weight > W:
          continue
        sub = 0
        sub += (product[0][len(product[0])-1]-product[0][a])
        sub += (product[1][len(product[1])-1]-product[1][b])
        sub += (product[2][len(product[2])-1]-product[2][c])
        sub += (product[3][len(product[3])-1]-product[3][d])
        if ans < sub:
          ans = sub
print(ans)

Solution (Python):
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

kijyun = li[0][0]

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

for i in li:
    omosa[i[0]-kijyun].append(i[1])

for i in range(len(omosa)):
    omosa[i].sort(reverse = True)

ma = 0

for i in range(len(omosa[0])+1):
    for j in range(len(omosa[1])+1):
        for k in range(len(omosa[2])+1):
            for l in range(len(omosa[3])+1):
                to_ka = omosa[0][:i]+omosa[1][:j]+omosa[2][:k]+omosa[3][:l]
                if i*kijyun+j*(kijyun+1)+k*(kijyun+2)+l*(kijyun+3) > w:
                    continue
                ma = max(ma,sum(to_ka))

print(ma)

Solution (Python):
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

jw = li[0][0]
omosa = [[] for _ in range(4)]

for i in li:
    omosa[i[0]-jw].append(i[1])

for i in range(len(omosa)):
    omosa[i].sort(reverse = True)

saidai = n
ma = 0

for i in range(len(omosa[0])+1):
    for j in range(len(omosa[1])+1):
        for k in range(len(omosa[2])+1):
            for l in range(len(omosa[3])+1):
                to_ka = omosa[0][:i]+omosa[1][:j]+omosa[2][:k]+omosa[3][:l]
                if i*jw+j*(jw+1)+k*(jw+2)+l*(jw+3) > w:
                    continue
                ma = max(ma,sum(to_ka))

print(ma)

Solution (Python):
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

jw = li[0][0]
omosa = [[] for _ in range(4)]

for i in li:
    omosa[i[0]-jw].append(i[1])

for i in range(len(omosa)):
    omosa[i].sort(reverse = True)

saidai = n
ma = 0

for i in range(len(omosa[0])+1):
    for j in range(len(omosa[1])+1):
        for k in range(len(omosa[2])+1):
            for l in range(len(omosa[3])+1):
                to_ka = omosa[0][:i]+omosa[1][:j]+omosa[2][:k]+omosa[3][:l]
                if i*jw+j*(jw+1)+k*(jw+2)+l*(jw+3) > w:
                    continue
                ma = max(ma,sum(to_ka))

print(ma)

Solution (Python):
import itertools
N,W=map(int,input().split())
item=[[] for i in range(4)]
for i in range(N):
    w,v=map(int,input().split())
    if(i==0):
        base=w
        item[0].append(v)
    else:
        item[w-base].append(v)
for i in range(4):
    item[i].sort(reverse=True)
l1=len(item[0]);l2=len(item[1]);l3=len(item[2]);l4=len(item[3])
res=0
for x in itertools.product(range(l1+1),range(l2+1),range(l3+1),range(l4+1)):
    if(x[0]*base+x[1]*(base+1)+x[2]*(base+2)+x[3]*(base+3)>W):
        continue
    tmp=sum(item[0][:x[0]])+sum(item[1][:x[1]])+sum(item[2][:x[2]])+sum(item[3][:x[3]])
    res=max(res,tmp)
print(res)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl() 
a = [inpl() for _ in range(n)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort(key = lambda x:x[0])
b = [[0] for _ in range(4)]
f = a[0][0]
ind = 0
for i in range(n):
    w,v = a[i]
    if w != f:
        ind += 1
        f = w
    b[ind].append(b[ind][-1] + v)
f = a[0][0]
v,x,y,z = [len(x) for x in b]

li = itertools.product(range(v),range(x),range(y),range(z))
res = 0
for tmp in li:
    
    ww = sum(tmp[i]*(f+i) for i in range(4))
    vv = sum(b[i][tmp[i]] for i in range(4))
    
    if ww <= W:
        res = max(res, vv)
print(res)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

n, w = map(int, readline().split())
wv = [tuple(map(int, readline().split())) for i in range(n)]
dp = defaultdict(int)
dp[0] = 0

for ww, v in wv:
    for xw, xv in list(dp.items()):
        if ww + xw <= w:
            dp[ww + xw] = max(dp[ww + xw], v + xv)
print(max(dp.values()))

Solution (Python):
def main():
    n, w_lim = map(int, input().split())
    group = {}
    min_w = 0
    for i in range(n):
        w, v = map(int, input().split())
        if i == 0:
            group = {x: [] for x in range(w, w + 4)}
            min_w = w
        group[w].append(v)
    length = [len(group[i]) + 1 for i in range(min_w, min_w + 4)]
    for i in range(min_w, min_w + 4):
        group[i].sort(reverse=True)
        for j in range(1, length[i - min_w] - 1):
            group[i][j] += group[i][j - 1]
        group[i] = [0] + group[i]
    answer = 0
    for i in range(length[0]):
        for j in range(length[1]):
            for k in range(length[2]):
                for l in range(length[3]):
                    if w_lim < min_w * i + (min_w + 1) * j + (min_w + 2) * k + (min_w + 3) * l:
                        break
                    answer = max(answer, group[min_w][i] + group[min_w + 1][j] + group[min_w + 2][k] + group[min_w + 3][l])
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl() 
a = [inpl() for _ in range(n)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort()
b = []
now = a[0][0]
li = []
for i in range(n):
    w,v = a[i]
    if now == w:
        li.append(v)
    else:
        now = w
        b.append(li)
        li = []
        li.append(v)
if li != []: b.append(li)
kind = now - a[0][0] + 1
f = a[0][0]
for i in range(len(b)):
    b[i] = b[i][::-1]

c = [[0] for _ in range(4)]
for i,l in enumerate(b):
    for x in l:
        c[i].append(c[i][-1] + x)
    c[i] = c[i]

ln = [len(x) for x in c]
res = 0
def chk(w,v):
    global res
    if w <= W:
        res = max(res, v)
x,y,z,w = ln

for i in range(x):
    for j in range(y):
        for k in range(z):
            for l in range(w):
                ww = i*f+j*(f+1)+k*(f+2)+l*(f+3)
                v = c[0][i] + c[1][j] + c[2][k] + c[3][l]
                if ww <= W: res = max(res, v)
                
print(res)