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())
vi = [[] for _ in range(4)]
wi0, vi0 = map(int, input().split())
vi[0].append(vi0)

for _ in range(n-1):
    wii, vii = map(int, input().split())
    vi[wii-wi0].append(vii)

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

ret = 0
for i in range(len(vi[3])):
    for j in range(len(vi[2])):
        for k in range(len(vi[1])):
            tw = i*(wi0+3)+j*(wi0+2)+k*(wi0+1)
            l = max(0,min(len(vi[0])-1,(w - tw)//wi0))
            tw += l*(wi0)
            if tw > w: continue
            tv = vi[3][i]+vi[2][j]+vi[1][k]+vi[0][l]
            ret = max(ret, tv)
print(ret)

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

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

memo = {}
def dp(i, capacity):
    if i == N:
        return 0
    if (i, capacity) in memo:
        return memo[(i, capacity)]
    ret = dp(i+1, capacity)
    w, v = WVs[i]
    if w <= capacity:
        ret2 = dp(i+1, capacity - w) + v
        ret = ret if ret > ret2 else ret2
    memo[(i, capacity)] = ret
    return ret

print(dp(0, W))

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    vl = {}
    vl[WV[0][0]] = list()
    vl[WV[0][0]+1] = list()
    vl[WV[0][0]+2] = list()
    vl[WV[0][0]+3] = list()
    for w, v in WV:
        vl[w].append(v)

    for v in vl.values():
        v.sort(reverse=True)
        v.insert(0, 0)


    wi, wj, wk, wl = vl.keys()
    ans = 0
    vis = 0
    for i, vi in enumerate(vl[wi]):
        if wi * i > W:
            break
        vis += vi
        vjs = 0
        for j, vj in enumerate(vl[wj]):
            if wi * i + wj * j > W:
                break
            vjs += vj
            vks = 0
            for k, vk in enumerate(vl[wk]):
                if wi*i + wj*j + wk*k> W:
                    break
                vks += vk
                vls = 0
                for l, vll in enumerate(vl[wl]):
                    if wi*i + wj*j + wk*k + wl*l> W:
                        break
                    vls += vll
                ans = max(ans, vis+vjs+vks+vls)
    return ans





def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]
    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from itertools import accumulate 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,W = map(int,readline().split())
A1 = []
A2 = []
A3 = []
A4 = []
w1,v1 = map(int,readline().split())
A1.append(v1)

for _ in range(N-1):
    w,v = map(int,readline().split())
    if w == w1:
        A1.append(v)
    elif w == w1+1:
        A2.append(v)
    elif w == w1+2:
        A3.append(v)
    else:
        A4.append(v)

S1 = list(accumulate(sorted(A1,reverse = True)))
S2 = list(accumulate(sorted(A2,reverse = True)))
S3 = list(accumulate(sorted(A3,reverse = True)))
S4 = list(accumulate(sorted(A4,reverse = True)))

S1 = [0] + S1
S2 = [0] + S2
S3 = [0] + S3
S4 = [0] + S4

ans = 0
for a in range(len(S1)):
    for b in range(len(S2)):
        for c in range(len(S3)):
            for d in range(len(S4)):
                tmp = w1*(a+b+c+d)+b+2*c+3*d
                total = S1[a]+S2[b]+S3[c]+S4[d]
                if tmp <= W:
                    ans = max(ans,total)
print(ans)

Solution (Python):
import sys
import math
import collections
import bisect
import itertools

import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    n, w = ns()
    w_list = []
    v_list = []
    for _ in range(n):
        wi, vi = ns()
        w_list.append(wi)
        v_list.append(vi)

    lim = 301
    base = w_list[0]
    dp = [[-1] * (lim + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for wi, vi in zip(w_list, v_list):
        wi -= base
        for i in range(n - 1, -1, -1):
            base_cost = (i + 1) * base
            for j in range(lim + 1):
                if dp[i][j] != -1:
                    if j + wi + base_cost <= w:
                        dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)

    ans = 0
    for dpi in dp:
        ans = max(ans, max(dpi))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,w = map(int,ipt().split())
    tng = [tuple(map(int,ipt().split())) for i in range(n)]
    dp = [[0]*(3*n) for i in range(n+1)]
    w1 = tng[0][0]
    ma = 0
    for ni,(wi,vi) in enumerate(tng):
        dw = wi-w1
        for i in range(ni+1,0,-1):
            for j in range(dw,3*n):
                if dp[i-1][j-dw]+vi > dp[i][j]:
                    dp[i][j] = dp[i-1][j-dw]+vi

    ans = 0
    for i in range(n+1):
        rw = w-i*w1
        if rw < 0:
            break
        ti = max(min(3*n-1,rw),0)
        if ans < dp[i][ti]:
            ans = dp[i][ti]


    print(ans)
    return None

if __name__ == '__main__':
    main()

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

w0 = wvs[0][0]
dp = [[[0]*(330) for i in range(110)] for k in range(110)]

for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(310):
            
            
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 >= 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

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

w0 = wvs[0][0]
dp = [[[-1]*(330) for i in range(110)] for k in range(110)]
dp[0][0][0] = 0
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(310):
            
            
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 >= 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

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

w0 = wvs[0][0]
dp = [[[-1]*(330) for i in range(110)] for k in range(110)]
dp[0][0][0] = 0
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(310):
            
            if dp[i][j][j] == -1:continue
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 >= 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

Solution (Python):
n,w=list(map(int,input().split()))
m=0
d={0:0}
for i in range(n):
  nd={}
  a,b=list(map(int,input().split()))
  for j in d:
    if j in nd:
      nd[j]=max(nd[j],d[j])
    else:
      nd[j]=d[j]
    if j+a>w:
      continue
    if j+a in nd:
      nd[j+a]=max(nd[j+a],d[j]+b)
    else:
      nd[j+a]=d[j]+b
    m=max(m,d[j]+b)
  d=nd
print(m)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,w = list(map(int, input().split()))
wv = [None]*n
for i in range(n):
    wv[i] = tuple(map(int, input().split()))
w0 = wv[0][0]
wv = [(item[0]-w0, item[1]) for item in wv]
ans = 0
def sub(k):
    W = w - k*w0
    m = min(W, sum(item[0] for item in wv))
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        iw, iv = wv[i-1]
        for j in range(m+1):
            for kk in range(1,k+1):
                if j>=iw:
                    dp[i][j][kk] = max(dp[i-1][j][kk], dp[i-1][j-iw][kk-1]+iv)
                else:
                    dp[i][j][kk] = dp[i-1][j][kk]

    return max(dp[n][j][kk] for j in range(m+1))
for k in range(1, w//w0+1):
    if k>n:
        break
    ans = max(ans, sub(k))
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,w = list(map(int, input().split()))
wv = [None]*n
for i in range(n):
    wv[i] = tuple(map(int, input().split()))
w0 = wv[0][0]
wv = [(item[0]-w0, item[1]) for item in wv]
ans = 0
def sub(k):
    W = w - k*w0
    m = min(W, sum(item[0] for item in wv))
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        iw, iv = wv[i-1]
        for j in range(m+1):
            for kk in range(1,k+1):
                if j>=iw:
                    dp[i][j][kk] = max(dp[i-1][j][kk], dp[i-1][j-iw][kk-1]+iv)
                else:
                    dp[i][j][kk] = dp[i-1][j][kk]

    return max(dp[n][j][kk] for j in range(m+1) for kk in range(k+1))
for k in range(1, w//w0+1):
    if k>n:
        break
    ans = max(ans, sub(k))
print(ans)

Solution (Python):
n,w=list(map(int,input().split()))
gds=[list(map(int,input().split())) for _ in range(n)]
w1=gds[0][0]
goods={w1+i:[0] for i in range(4)}

for cw,cv in gds:
    goods[cw].append(cv)

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

for d in range(min(w//(w1+3),len(goods[w1+3]))+1):
    wd=w-d*(w1+3)
    for c in range(min(wd//(w1+2),len(goods[w1+2]))+1):
        wc=wd-c*(w1+2)
        for b in range(min(wc//(w1+1),len(goods[w1+1]))+1):
            wb=wc-b*(w1+1)
            a=wb//w1

            ans=max(ans,sum(goods[w1][:a])+sum(goods[w1+1][:b])+sum(goods[w1+2][:c])+sum(goods[w1+3][:d]))

print(ans)

Solution (Python):
from collections import defaultdict
n, W = map(int, input().split())
d = defaultdict(int)
d[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j, k in list(d.items()):
        if W >= j + w:
            d[j + w] = max(d[j + w], k + v)
print(max(d.values()))

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n,ww=MI()
	w1,v1=MI()
	li=[[] for _ in range(4)]
	li[0].append(v1)

	for _ in range(n-1):
		w,v=MI()
		li[w-w1].append(v)

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

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

	ans=0

	for i0 in range(len(li[0])):
		for i1 in range(len(li[1])):
			for i2 in range(len(li[2])):
				for i3 in range(len(li[3])):
					
					if w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3<=ww:
						ans=max(ans,li[0][i0]+li[1][i1]+li[2][i2]+li[3][i3])

	print(ans)


if __name__ == "__main__":
	main()

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n,ww=MI()
	w1,v1=MI()
	li=[[] for _ in range(4)]
	li[0].append(v1)

	for _ in range(n-1):
		w,v=MI()
		li[w-w1].append(v)

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

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

	ans=0

	for i0 in range(len(li[0])):
		for i1 in range(len(li[1])):
			for i2 in range(len(li[2])):
				for i3 in range(len(li[3])):
					
					if w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3<=ww:
						ans=max(ans,li[0][i0]+li[1][i1]+li[2][i2]+li[3][i3])

	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,w = map(int,readline().split())
wv = list(map(int,read().split()))

inf = -1 * 10**10
dp = [[inf] * (301) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    wi,vi = wv[i*2:i*2+2]
    wi -= wv[0]
    for j in range(n,0,-1):
        for k in range(wi,301):
            dp[j][k] = max(dp[j][k], dp[j-1][k-wi] + vi)

ans = 0
for i in range(n+1):
    for j in range(301):
        if(i*wv[0] + j <= w):
            ans = max(ans,dp[i][j])

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N, W = map(int, input().split())
    V = [[0] for _ in range(4)]
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0:
            init = w
        V[w - init].append(v)

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

    res = 0
    for i in range(len(V[0]) + 1):
        a = sum(V[0][:i])
        for j in range(len(V[1]) + 1):
            b = sum(V[1][:j])
            for k in range(len(V[2]) + 1):
                c = sum(V[2][:k])
                for l in range(len(V[3]) + 1):
                    d = sum(V[3][:l])
                    total_w = init * i + (init + 1) * j + (init + 2) * k + (init + 3) * l
                    if total_w <= W:
                        res = max(res, a + b + c + d)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N, W = map(int, input().split())
    V = [[0] for _ in range(4)]
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0:
            init = w
        V[w - init].append(v)

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

    res = 0
    for i in range(len(V[0]) + 1):
        a = sum(V[0][:i])
        for j in range(len(V[1]) + 1):
            b = sum(V[1][:j])
            for k in range(len(V[2]) + 1):
                c = sum(V[2][:k])
                for l in range(len(V[3]) + 1):
                    d = sum(V[3][:l])
                    total_w = init * i + (init + 1) * j + (init + 2) * k + (init + 3) * l
                    if total_w <= W:
                        res = max(res, a + b + c + d)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N, W = na()
INF = 10 ** 12
dp = [[-INF] * (N*3+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = na()
    if i == 0:
        w1 = w
    w -= w1
    for j in range(N, 0, -1):
        for k in range(N*3, -1, -1):
            if k >= w:
                dp[j][k] = max(dp[j][k], dp[j-1][k-w] + v)

ans = 0
for i in range(1, N+1):
    wmax = W - w1 * i
    if wmax < 0:
        break
    ans = max(ans, max(dp[i][0:min(N, wmax) + 1]))

print(ans)

Solution (Python):
N, W = (int(x) for x in input().split())
dp = [[-1 for i in range(301)] for j in range(N+1)]
dp[0][0] = 0
for k in range(N):
    w, v = (int(x) for x in input().split())
    if k == 0:
        base_w = w
    for i in range(N)[::-1]:    
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base_w] = max([dp[i][j]+v, dp[i+1][j+w-base_w]])
        
ans=0
for index,item in enumerate(dp):
    if W-index*base_w+1<=0:
        break
    ans=max(max(item[:W-index*base_w+1]),ans)

print(ans)

Solution (Python):
from itertools import accumulate

n, W = (int(x) for x in input().split())
WV = [tuple(int(x) for x in input().split()) for _ in range(n)]
weight = [[] for _ in range(4)]  
w1 = WV[0][0]
for w, v in WV:
    weight[w - w1].append(v)

for wei in weight:
    wei.sort(reverse=True)

value_acc = [[] for _ in range(4)]
for i in range(4):
    value_acc[i] = list(accumulate(weight[i]))

ans = 0
for i in range(len(weight[0]) + 1):
    for j in range(len(weight[1]) + 1):
        for k in range(len(weight[2]) + 1):
            for l in range(len(weight[3]) + 1):
                tmp = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                if tmp <= W:
                    value = 0
                    for x, y in zip([0, 1, 2, 3], [i, j, k, l]):
                        if y - 1 >= 0:
                            value += value_acc[x][y - 1]
                    ans = max(ans, value)

print(ans)

Solution (Python):
from collections import defaultdict

n, W = (int(x) for x in input().split())
WV = [tuple(int(x) for x in input().split()) for _ in range(n)]
d = defaultdict(int)  
d[0] = 0
for i in range(n):
    w, v = WV[i]
    d_tmp = list(d.items())
    for w_sum, v_sum in d_tmp:
        if w_sum + w <= W:
            d[w_sum + w] = max(d[w_sum + w], v_sum + v)

print(max(d.values()))

Solution (Python):
N,W = map(int,input().split())
a,b,c,d = [],[],[],[]
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w0 = w
    if w == w0:
        a.append(v)
    elif w == w0+1:
        b.append(v)
    elif w == w0+2:
        c.append(v)
    else:
        d.append(v)
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
d.sort(reverse=True)
A,B,C,D = len(a),len(b),len(c),len(d)
a1 = [0]*(A+1)
b1 = [0]*(B+1)
c1 = [0]*(C+1)
d1 = [0]*(D+1)
for i in range(1,A+1):
    a1[i] = a1[i-1] + a[i-1]
for i in range(1,B+1):
    b1[i] = b1[i-1] + b[i-1]
for i in range(1,C+1):
    c1[i] = c1[i-1] + c[i-1]
for i in range(1,D+1):
    d1[i] = d1[i-1] + d[i-1]
ans = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            for l in range(D+1):
                if w0*i + (w0+1)*j + (w0+2)*k + (w0+3)*l <= W:
                    ans = max(ans,a1[i]+b1[j]+c1[k]+d1[l])
                else:
                    break
print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,W,*wv = map(int,read().split())

res = [[] for _ in range(n)]
w0 = wv[0]
mp = iter(wv)
for w,v in zip(mp,mp):
    res[w-w0].append(v)

from itertools import accumulate
d = [None for _ in range(4)]
for i in range(4):
    r = res[i]
    r.sort(reverse=True)
    d[i] = {(w0+i)*(j+1):wj for j,wj in enumerate(accumulate(r))}
    d[i][0] = 0
    
    

def merge(d1,d2):
    res = {}
    for w1,v1 in d1.items():
        for w2,v2 in d2.items():
            w = w1+w2
            v = v1+v2
            if w in res: res[w] = max(res[w],v)
            else: res[w] = v
    return res    



d1 = merge(d[0],d[1])
d2 = merge(d[2],d[3])
dd = merge(d1,d2)






ans = 0
for w,v in dd.items():
    if w <= W and ans < v:
        ans = v
print(ans)

Solution (Python):
from collections import Counter, deque, OrderedDict, defaultdict




from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product









import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    for i in d.values():
        i.sort(reverse=True)

    
    from collections import OrderedDict
    d = OrderedDict(sorted(d.items()))

    
    

    dlength = []
    for k, v in d.items():
        dlength.append((range(len(v)+1), k, v))

    for i in range(4-len(dlength)):
        dlength.append((range(1), 0, [0]))
    Mans = 0
    for i in dlength[0][0]:
        for j in dlength[1][0]:
            for k in dlength[2][0]:
                for l in dlength[3][0]:
                    if i*dlength[0][1]+j*dlength[1][1]+k*dlength[2][1]+l*dlength[3][1] <= W:
                        Mans = max(Mans, sum(
                            dlength[0][2][:i])+sum(dlength[1][2][:j])+sum(dlength[2][2][:k])+sum(dlength[3][2][:l]))

    print(Mans)


resolve()

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

for i in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

dp = {}
dp.setdefault(0, {})
dp[0][0] = 0

for i in range(N):
    weight_list = sorted(dp.keys(), reverse=True)
    for w in weight_list:
        dp.setdefault(w + weights[i], {})
        dp[w + weights[i]][i + 1] = max(
            max(dp[w].values()) + values[i],
            dp[w + weights[i]].get(i + 1, 0)
        )


res = 0
for w, prefix in dp.items():
    if w <= W:
        res = max(res, max(prefix.values()))

print(res)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, W = mapint()
wv = [list(mapint()) for _ in range(N)]
w0 = wv[0][0]

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

for i in range(1, N+1):
    w, v = wv[i-1]
    w -= w0
    for j in range(1, i+1):
        for k in range(3*N+1):
            dp[i][j][k] = dp[i-1][j][k]
            if w<=k:
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-w]+v)

ans = 0
for i in range(N+1):
    if W<i*w0:
        break
    ans = max(ans, max(dp[N][i][:W-i*w0+1]))
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,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)]
gds = [[0] for _ in range(4)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort(key = lambda x:x[0])

mi = a[0][0]
for i,(w,v) in enumerate(a):
    ind = w - mi
    gds[ind].append(v)
we = [i+mi for i in range(4)]
cnt = [0] * 4
for i in range(4):
    cnt[i] = len(gds[i])
    tmp = itertools.accumulate(gds[i])
    gds[i] = list(tmp)

it = itertools.product(range(cnt[0]),range(cnt[1]),range(cnt[2]),range(cnt[3]))
res = 0
for ww in it:
    if sum(we[i]*ww[i] for i in range(4)) > W: continue
    now = sum(gds[i][ww[i]] for i in range(4))
    res = max(now, res)
print(res)

Solution (Python):
N,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
w1 = A[0][0]
C = {0:[],1:[],2:[],3:[]}
for i in range(N):
    w,v = A[i]
    C[w-w1].append(v)
C[0] = sorted(C[0],reverse=True)
C[1] = sorted(C[1],reverse=True)
C[2] = sorted(C[2],reverse=True)
C[3] = sorted(C[3],reverse=True)
n0 = len(C[0])
n1 = len(C[1])
n2 = len(C[2])
n3 = len(C[3])
vmax = 0
for a0 in range(n0+1):
    for a1 in range(n1+1):
        for a2 in range(n2+1):
            for a3 in range(n3+1):
                if a0*w1+a1*(w1+1)+a2*(w1+2)+a3*(w1+3)<=W:
                    v = sum(C[0][:a0])+sum(C[1][:a1])+sum(C[2][:a2])+sum(C[3][:a3])
                    vmax = max(vmax,v)
print(vmax)

Solution (Python):
import sys



from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def solve():
    N, W = getList()
    MI = 100
    MJ = 300
    sina = []
    w, v = getList()
    w1 = w
    v1 = v
    
    for i in range(N-1):
        w, v = getList()
        sina.append((w - w1, v))

    dp = [-1 for i in range(MI*MJ+MI+MJ)]
    dp[0] = 0
    dp[MJ] = v1
    for w, v in sina:
        
        nxt = [-1 for i in range(MI*MJ+MI+MJ)]
        for i in range(MI):
            for j in range(MJ):
                cur = dp[i*MJ + j]
                if cur != -1:
                    if nxt[i * MJ + j] < cur:
                        nxt[i * MJ + j] = cur
                    
                    
                    if nxt[(i+1) * MJ + j + w] < cur + v:
                        nxt[(i + 1) * MJ + j + w] = cur + v
                        

        dp = nxt
        
        

    ans = 0
    for i in range(MI):
        for j in range(MJ):
            
            if w1 * i + j <= W:

                if dp[i*MJ + j] > ans:
                    
                    ans = dp[i * MJ + j]

    print(ans)






def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    
    solve()

Solution (Python):

import sys
def main(N, W, items):
    w1 = items[0][0]
    dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        iw, iv = items[i]
        iw -= w1
        for j in range(N + 1):
            for w in range(3 * N + 1):
                if j * w1 + w > W: break
                if w >= iw and j >= 1:
                    dp[i + 1][j][w] = max(dp[i][j][w], dp[i][j - 1][w - iw] + iv)
                else:
                    dp[i + 1][j][w] = dp[i][j][w]
    ans = 0
    for j in range(N + 1):
        for w in range(3 * N + 1):
            ans = max(ans, dp[N][j][w])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)

Solution (Python):
from collections import defaultdict
N,W=map(int, input().split())
Ws=[]
Vs=[]
for i in range(N):
    w,v=map(int, input().split())
    Ws.append(w)
    Vs.append(v)

D=defaultdict(int)
D[0]=0


for i in range(N):
    w=Ws[i]
    v=Vs[i]
    A=list( D.items())
    for dw,dv in A:
        
        if dw+w<=W:
            D[dw+w]=max(D[dw+w], v+dv)


print(max(D.values()))

Solution (Python):
import sys
input = sys.stdin.readline
import itertools
n,w = map(int,input().split())
c = []
s = 0
for i in range(n):
  a,v = map(int,input().split())
  s += a
  c.append((a,v))
  
r = c[0][0]
L = min(100,w//r)
m = s-r*n+1
dp = [[[-float('inf')]*m for i in range(L+1)] for i in range(n+1)]
for i in range(n):
  dp[i][0][0] = 0

for i in range(n):
  for j in range(L):
    for k in range(m):
      W,V = c[i]
      R = W-r
      if k-R >= 0 and r*(j+1)+k <= w:
        dp[i+1][j+1][k] = max(dp[i][j+1][k],dp[i][j][k-R]+V)
      else:
        dp[i+1][j+1][k] = dp[i][j+1][k]
        
print(max(0,max(list(itertools.chain.from_iterable(dp[n])))))