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())
WV = [list(map(int,input().split())) for _ in range(N)]

Wdic = {}
for w in WV:
  if w[0] not in Wdic:
    Wdic[w[0]] = [w]
  else:
    Wdic[w[0]].append(w)

Wcount = [[0 for _ in range(2)] for _ in range(4)]
idx = 0
for k in Wdic.keys():
  Wcount[idx] = [k,len(Wdic[k])]
  idx += 1


Wsum = {}
for k,v in Wdic.items():
  v.sort(key=lambda x:x[1], reverse = True)
  Wsum[k] = [v[0][1]]
  for i in range(1,len(v)):
    Wsum[k].append(Wsum[k][-1] + v[i][1])


def check(i,j,k,l):
  ret = 0
  w = 0
  if i > 0 and Wcount[0][0] > 0:
    ret += Wsum[Wcount[0][0]][i-1]
    w += Wcount[0][0]*i
  if j > 0 and Wcount[1][0] > 0:
    ret += Wsum[Wcount[1][0]][j-1]
    w += Wcount[1][0]*j
  if k > 0 and Wcount[2][0] > 0:
    ret += Wsum[Wcount[2][0]][k-1]
    w += Wcount[2][0]*k
  if l > 0 and Wcount[3][0] > 0:
    ret += Wsum[Wcount[3][0]][l-1]
    w += Wcount[3][0]*l
  if w > W:
    ret = 0
  return ret

value = 0
for i in range(Wcount[0][1]+1):
  for j in range(Wcount[1][1]+1):
    for k in range(Wcount[2][1]+1):
      for l in range(Wcount[3][1]+1):
        value = max(value,check(i,j,k,l))
print(value)

Solution (Python):


N,WW = list(map(int,input().split(" ")))

things = [list(map(int,input().split(" "))) for _ in range(N )]
W,v = things[0]
dic = {}
dic[W] = [v]
for i in range(1,4):
    dic[W + i] = []
for temp in things[1:]:
    w,v = temp
    dic[w].append(v)
ans = 0
l1 = len(dic[W])
l2 = len(dic[W + 1])
l3 = len(dic[W + 2])
l4 = len(dic[W + 3])
dic[W].sort(reverse=True)
dic[W + 1].sort(reverse=True)
dic[W + 2].sort(reverse=True)
dic[W + 3].sort(reverse=True)
for i1 in range(l1 + 1):
    for i2 in range(l2 + 1):
        for i3 in range(l3 + 1):
            for i4 in range(l4 + 1):
                temp = sum(dic[W][:i1]) + sum(dic[W+1][:i2]) + sum(dic[W+2][:i3]) + sum(dic[W+ 3][:i4])

                if  W * i1 +  (W +1) * i2 + (W +2) * i3 +  (W +3) * i4 <= WW:
                    ans = max(temp,ans)
print(ans)

Solution (Python):
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,W = LI()
    dic = {}
    dic[0] = 0

    for i in range(N):
        w,v = LI()
        dic_nxt = {k:dic[k] for k in dic}
        for k in dic:
            if k+w<=W:
                dic_nxt[k+w] = max(dic_nxt.get(k+w,0),dic.get(k,0)+v)
        dic = {k:dic_nxt[k] for k in dic_nxt}
    return(max(dic.values()))

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

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

from collections import defaultdict
List = []
dp = []*(N+1)
for i in range(N+1):
    dp.append(defaultdict(lambda : -float("inf")))
for i in range(N+1):
    dp[i][0] = 0


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

for i in range(N):
    w,v = List[i]
    for j in list(dp[i]):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j+w <= W:
            dp[i+1][j+w] = max(dp[i][j+w], dp[i][j]+v)
ans = -float("inf")
for i in dp[N]:
    ans = max(ans,dp[N][i])
    
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]
WV.sort()

vlist = [[] for i in range(4)]
for i in range(N):
    w,v = WV[i][0],WV[i][1]
    d = w-w1
    vlist[d].append(v)
    
vrui = [[0] for i in range(4)]
for i in range(4):
    vlist[i].sort(reverse=True)
    for v in vlist[i]:
        vrui[i].append(vrui[i][-1]+v)
        


MAX = 0
for i in range(min(N+1,len(vlist[0])+1)):
    for j in range(min(N-i+1,len(vlist[1])+1)):
        for k in range(min(N-i-j+1,len(vlist[2])+1)):
            for l in range(min(N-(i+j+k)+1,len(vlist[3])+1)):
                
                
                
                if (w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l) <= W:
                    MAX = max(MAX,(vrui[0][i]+vrui[1][j]+vrui[2][k]+vrui[3][l]))

print(MAX)

Solution (Python):

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
w0 = wv[0][0]
weights = [wv[0][0],wv[0][0]+1,wv[0][0]+2,wv[0][0]+3]
wdict = {}
cnt = 0
for w in weights:
    wdict[w] = cnt
    cnt += 1
values = [[] for _ in range(4)]

for w,v in wv:
    values[wdict[w]].append(v)

sums = 0
for i in range(4):
    values[i].sort(reverse = True)
    sums += sum(values[i])
    
ruisekiwa = [[0]*(N+1) for _ in range(4)]
for i in range(4):
    ruisekiwa[i][0] = 0
    for j in range(1,len(values[i])+1):
        ruisekiwa[i][j] = ruisekiwa[i][j-1] + values[i][j-1] 
    
ans = 0
for i in range(len(values[0])+1):
    for j in range(len(values[1])+1):
        for k in range(len(values[2])+1):
            for l in range(len(values[3])+1):
                w_tmp = w0*i + (w0+1)*j + (w0+2)*k + (w0+3) * l

                if w_tmp <= W:
                    val = ruisekiwa[0][i] + ruisekiwa[1][j] + ruisekiwa[2][k] + ruisekiwa[3][l]
                    ans = max(ans,val)
                    
print(ans)

Solution (Python):

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
w0 = wv[0][0]
weights = [wv[0][0],wv[0][0]+1,wv[0][0]+2,wv[0][0]+3]
wdict = {}
cnt = 0
for w in weights:
    wdict[w] = cnt
    cnt += 1
values = [[] for _ in range(4)]

for w,v in wv:
    values[wdict[w]].append(v)

sums = 0
for i in range(4):
    values[i].sort(reverse = True)
    sums += sum(values[i])
    
ruisekiwa = [[0]*(N+1) for _ in range(4)]
for i in range(4):
    ruisekiwa[i][0] = 0
    for j in range(1,len(values[i])+1):
        ruisekiwa[i][j] = ruisekiwa[i][j-1] + values[i][j-1] 
    
ans = 0
for i in range(len(values[0])+1):
    for j in range(len(values[1])+1):
        for k in range(len(values[2])+1):
            for l in range(len(values[3])+1):
                w_tmp = w0*i + (w0+1)*j + (w0+2)*k + (w0+3) * l

                if w_tmp <= W:
                    val = ruisekiwa[0][i] + ruisekiwa[1][j] + ruisekiwa[2][k] + ruisekiwa[3][l]
                    ans = max(ans,val)
                    
print(ans)

Solution (Python):
from itertools import accumulate
N, W = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)

for _ in range(N - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0



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

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

V = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        V[0].append(v)
    else:
        V[w-w0].append(v)
J = []
for i in range(4):
    F = sorted(V[i], reverse=True)
    G = [0]
    for f in F:
        G.append(f+G[-1])
    J.append(G)

ans = 0
for s0 in range(len(J[0])):
    for s1 in range(len(J[1])):
        for s2 in range(len(J[2])):
            for s3 in range(len(J[3])):
                if s0*w0 + s1*(w0+1) + s2*(w0+2) + s3*(w0+3) > W:
                    continue
                ans = max(ans, J[0][s0]+J[1][s1]+J[2][s2]+J[3][s3])
print(ans)

Solution (Python):

from itertools import accumulate


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  
    for i in range(0, 2 * N, 2):
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                for l in range(L[3]):
                    w = i * x + j * (x + 1) + k * (x + 2) + l * (x + 3)
                    if w > W:
                        break
                    v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                    ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  
    for i in range(0, 2 * N, 2):
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate
n, w = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)
for _ in range(n - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0
for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if ((i) * w_0) + ((j) * (w_0 + 1)) + ((k) * (w_0 + 2)) + (((l) * (w_0 + 3))) <= w:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)

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

for i in range(n):
    v[wv[i][0]-wv[0][0]].append(wv[i][1])

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

ans=0
for i in range(len(v[0])+1):
    tmp=[[0,0] for t in range(4)]        
    tmp[0][0]=sum(v[0][:i])
    tmp[0][1]=wv[0][0]*i
    for j in range(len(v[1])+1):
        tmp[1][0]=sum(v[1][:j])
        tmp[1][1]=(wv[0][0]+1)*j
        for k in range(len(v[2])+1):
            tmp[2][0]=sum(v[2][:k])
            tmp[2][1]=(wv[0][0]+2)*k
            for l in range(len(v[3])+1):
                tmp[3][0]=sum(v[3][:l])
                tmp[3][1]=(wv[0][0]+3)*l
                if tmp[0][1]+tmp[1][1]+tmp[2][1]+tmp[3][1]<=w:
                    ans=max(ans,tmp[0][0]+tmp[1][0]+tmp[2][0]+tmp[3][0])
print(ans)

Solution (Python):
n,W = map(int,input().split())
w1,v = map(int,input().split())
c = [[] for _ in range(4)]
c[0].append(v)
for i in range(n-1):
    w,v = map(int,input().split())
    c[w-w1].append(v)

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

l = [len(c[i]) for i in range(4)]
sum_c = []
for _ in range(4):
    k = [0]
    for i in range(l[_]):
        k.append(k[-1] + c[_][i])
    sum_c.append(k)
ans = 0
for p1 in range(l[0]+1):
    for p2 in range(l[1]+1):
        for p3 in range(l[2]+1):
            for p4 in range(l[3]+1):
                now = w1*p1+(w1+1)*p2+(w1+2)*p3+(w1+3)*p4
                if now<=W:
                    ans = max(ans,sum_c[0][p1]+sum_c[1][p2]+sum_c[2][p3]+sum_c[3][p4])
                    


print(ans)

Solution (Python):
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]
dp=[{} for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    p=dp[i].keys()
    for w in p:
        dp[i+1][w]=dp[i][w]
    for w in p:
        wn=w+wv[i][0]
        if wn<=W and (wn not in dp[i+1] or dp[i+1][wn]<dp[i][w]+wv[i][1]):
                dp[i+1][wn]=dp[i][w]+wv[i][1]
print(max(dp[N].values()))

Solution (Python):
N,W=map(int,input().split())
goods=[[] for i in range(4)]
w1=-1
for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        w1=w
    goods[w-w1].append(v)
S=[]
for x in range(4):
    goods[x].sort(reverse=True)
    G=goods[x]
    now=[0]*(len(G)+1)
    for i in range(len(G)):
        now[i+1]=now[i]+G[i]
    S.append(now)
ans=0
for i in range(1+len(goods[0])):
    for j in range(1+len(goods[1])):
        for k in range(1+len(goods[2])):
            wnow=W-w1*(i+j+k)-j-2*k
            if wnow<0:
                continue
            else:
                ans=max(ans,S[0][i]+S[1][j]+S[2][k]+S[3][min(len(S[3])-1,wnow//(w1+3))])
print(ans)

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

from itertools import accumulate

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, w = li()
value = {i: [] for i in range(4)}

for i in range(n):
    wei, val = li()

    if i == 0:
        w0 = wei

    value[wei - w0].append(val)

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

    value[i] = [0] + list(accumulate(value[i]))


ans = 0

for i in range(len(value[0])):
    for j in range(len(value[1])):
        for k in range(len(value[2])):
            rest = w - i*w0 - j*(w0+1) - k*(w0+2)
            x = rest // (w0+3)

            if x < 0:
                continue
            else:
                ans = max(ans, value[0][i] + value[1][j] + value[2][k] + value[3][min(len(value[3])-1, x)])

print(ans)

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

from itertools import accumulate

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, w = li()
value = {i: [] for i in range(4)}

for i in range(n):
    wei, val = li()

    if i == 0:
        w0 = wei

    value[wei - w0].append(val)

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

    value[i] = [0] + list(accumulate(value[i]))


ans = 0

for i in range(len(value[0])):
    for j in range(len(value[1])):
        for k in range(len(value[2])):
            rest = w - i*w0 - j*(w0+1) - k*(w0+2)
            x = rest // (w0+3)

            if x < 0:
                continue
            else:
                ans = max(ans, value[0][i] + value[1][j] + value[2][k] + value[3][min(len(value[3])-1, x)])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,w=map(int,input().split())

w1,v1=map(int,input().split())
W,V=[0],[v1]
for i in range(n-1):
  wi,vi=map(int,input().split())
  W.append(wi-w1)
  V.append(vi)
DP=[[[0]*(n+1) for _ in range(3*n+1)] for __ in range(n+1)]
for i in range(1,n+1):
  for j in range(3*i+1):
    for k in range(1,i+1):
      if j<W[i-1]:
        DP[i][j][k]=DP[i-1][j][k]
      else:
        DP[i][j][k]=max(DP[i-1][j-W[i-1]][k-1]+V[i-1],DP[i-1][j][k])
ans=0
for j in range(3*n+1):
  for k in range(n+1):
    if j+w1*k<=w:
      ans=max(ans,DP[n][j][k])
print(ans)

Solution (Python):
N,W=map(int,input().split())
wv=[]
for i in range(N):
    a,b=map(int,input().split())
    wv.append((a,b))
if wv[0][0]<300:
    dp=[[0]*(30000+1) for i in range(N+1)]
    for i in range(1,N+1):
        wi,vi=wv[i-1]
        for j in range(1,30000+1):
            dp[i][j]=dp[i-1][j]
            if j-wi<0:
                continue
            dp[i][j]=max(dp[i-1][j-wi]+vi,dp[i][j])
    ans=dp[N][W]
    print(ans)
    quit()
dp=[[0]*(301*101) for i in range(N+1)]
d=wv[0][0]
def change(n):
    return 301*(n//d)+min(n%d,300)


for i in range(1,N+1):
    wi,vi=wv[i-1]
    z=301+(wi-d)
    for j in range(1,301*101):
        dp[i][j]=dp[i-1][j]
        if j-z<0:
            continue

        dp[i][j]=max(dp[i-1][j-z]+vi,dp[i][j])
ans=dp[N][change(W)]
print(ans)

Solution (Python):
N,W=map(int,input().split())
w0,v=map(int,input().split())
goods=[[v],[],[],[]]
for i in range(N-1):
    w,v=map(int,input().split())
    goods[w-w0].append(v)
val=[]
for x in range(4):
    goods[x].sort(reverse=True)
    valx=[0]*(len(goods[x])+1)
    for k in range(len(goods[x])):
        valx[k+1]=valx[k]+goods[x][k]
    val.append(valx)
ans=0
for i in range(len(goods[0])+1):
    if w0*i>W:
        break
    for j in range(len(goods[1])+1):
        if w0*(i+j)+j>W:
            break
        for k in range(len(goods[2])+1):
            if w0*(i+j+k)+j+2*k>W:
                break
            for l in range(len(goods[3])+1):
                if w0*(i+j+k+l)+j+2*k+3*l>W:
                    break
                ans=max(ans,val[0][i]+val[1][j]+val[2][k]+val[3][l])
print(ans)

Solution (Python):

import sys
from itertools import accumulate, product





def solve(N: int, W: int, ws: "List[int]", vs: "List[int]"):
    w0 = ws[0]
    items = [[] for _ in range(4)]
    accum = [[] for _ in range(4)]
    for w, v in zip(ws, vs):
        items[w-w0].append(v)
    for i in range(4):
        items[i].sort(reverse=True)
        accum[i] = [0] + list(accumulate(items[i]))
    count = [len(items[i]) for i in range(4)]
    
    res = 0
    for nums in product(*[range(count[i] + 1) for i in range(4)]):
        w = sum((w0+i) * nums[i] for i in range(4))
        if w > W:
            continue
        v = sum(accum[i][nums[i]] for i in range(4))
        res = max(v, res)
    
    print(res)
    return



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))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate, product


N, W = map(int, input().split())
w, v = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


u = [
    [0] + list(
        accumulate(
            sorted(
                (
                    y for x, y in zip(w, v)
                    if x == i
                ),
                reverse=True
            )
        )
    )
    for i in range(w[0], w[0] + 4)
]



ans = max(
    sum(u[i][k] for i, k in enumerate(t)) +
    u[3][
        min(
            len(u[3]) - 1,
            (W - sum(k * (w[0] + i) for i, k in enumerate(t))) // (w[0] + 3)
        )
    ]
    for t in product(*map(range, map(len, u[:3])))
    if sum(k * (w[0] + i) for i, k in enumerate(t)) <= W
)


print(ans)

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

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

x = a[0][0]

for i in range(n):
    a[i][0]-=x

dp = [[[0 for i in range(301)] for j in range(n+1)] for k in range(n+1)]

for k in range(1,n+1):
    for j in range(1,n+1):
        for i in range(301):
            if i>=a[k-1][0]:
                dp[k][j][i]=max(dp[k-1][j-1][i-a[k-1][0]] + a[k-1][1], dp[k-1][j][i])
            else:
                dp[k][j][i]=dp[k-1][j][i]

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

print(ans)

Solution (Python):
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce

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

memo = {}

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

    if (i, j) in memo:
        return memo[i, j]
    elif j < w[i-1]:
        temp = nap(i-1, j)
    else:
        temp = max(nap(i-1, j), nap(i-1, j-w[i-1]) + v[i-1])

    memo[i,j] = temp

    return memo[i,j]

print(nap(N, W))

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

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

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


L[0].append(A[0])
P=0
for i in range(1,N):
    if A[i][0]==A[i-1][0]:
        L[P].append(A[i])
    else:
        P+=1
        L[P].append(A[i])

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

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

we=[0,0,0,0]
for i in range(4):
    if L[i]==[]:
        pass
    else:
        we[i]=L[i][0][0]
ans=0
for a in range(len(S[0])):
    for b in range(len(S[1])):
        for c in range(len(S[2])):
            for d in range(len(S[3])):
                v=S[0][a]+S[1][b]+S[2][c]+S[3][d]
                w=we[0]*a+we[1]*b+we[2]*c+we[3]*d
                if W>=w and ans<v:
                    ans=v
print(ans)

Solution (Python):
from collections import*
import functools
import sys
input=sys.stdin.readline
@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 print(max(d.values()))
N,W=map(int,input().split())   
d=defaultdict(int)
d[0]=0
if __name__=='__main__':
  Knapsack(N,W)

Solution (Python):
from collections import*
import functools
import sys
input=sys.stdin.readline
@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):
import itertools
n,w = map(int,input().split())

d = dict()
p = dict()
for i in range(n):
    u,v = map(int,input().split())
    if d.__contains__(u):
        d[u]+=1
    else:
        d[u]=1
    if p.__contains__(u):
        p[u].append(v)
    else:
        p[u]=[v]

for k in p.keys():
    p[k].sort(reverse=True)
    acc = [0]
    for c in p[k]:
        acc.append(acc[-1]+c)
    p[k]=acc

d = list(d.items())
p = [p[item[0]] for item in d]
g = [item[0] for item in d]
d = [range(item[1]+1)for item in d]
res = 0
for t in itertools.product(*d):
    if(sum([g[i]*t[i] for i in range(len(t))])<=w):
        res = max(res,sum([p[i][t[i]] for i in range(len(t))]))
print(res)

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

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = {i : {} for i in range(N)}

def dfs(i, j):
    if i == N:
        return 0
    elif j in memo[i]:
        return memo[i][j]
    elif A[i][0] > j:
        ans = dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
    memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Solution (Python):
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

s = [[0] for _ in range(4)]
for i in range(4):
    vs[i].sort()
    for j in range(len(vs[i])):
        s[i].append(s[i][-1] + vs[i][-j-1])

ans = 0
for i in range(N + 1):
    if i > len(vs[0]):
        break
    if i * w1 > W:
        break
    si = s[0][i]
    for j in range(N + 1 - i):
        if j > len(vs[1]):
            break
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        sj += s[1][j]
        for k in range(N + 1 - i - j):
            if k > len(vs[2]):
                break
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            sk += s[2][k]
            for l in range(N + 1 - i - j - k):
                if l > len(vs[3]):
                    break
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk
                sl += s[3][l]
                ans = max(ans, sl)
print(ans)

Solution (Python):
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

s = [[0] for _ in range(4)]
for i in range(4):
    vs[i].sort()
    for j in range(len(vs[i])):
        s[i].append(s[i][-1] + vs[i][-j-1])

ans = 0
for i in range(N + 1):
    if i > len(vs[0]):
        break
    if i * w1 > W:
        break
    si = s[0][i]
    for j in range(N + 1 - i):
        if j > len(vs[1]):
            break
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        sj += s[1][j]
        for k in range(N + 1 - i - j):
            if k > len(vs[2]):
                break
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            sk += s[2][k]
            for l in range(N + 1 - i - j - k):
                if l > len(vs[3]):
                    break
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk
                sl += s[3][l]
                ans = max(ans, sl)
print(ans)

Solution (Python):
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort()

ans = 0
for i in range(N + 1):
    if i * w1 > W:
        break
    if i == 0:
        si = 0
    else:
        si = sum(vs[0][-i:])
    for j in range(N + 1 - i):
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        if j > 0:
            sj += sum(vs[1][-j:])
        for k in range(N + 1 - i - j):
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            if k > 0:
                sk += sum(vs[2][-k:])
            for l in range(N + 1 - i - j - k):
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk               
                if l > 0:
                    sl += sum(vs[3][-l:])
                ans = max(ans, sl)
print(ans)

Solution (Python):
from collections import defaultdict
N, W = map(int, input().split())
dp = defaultdict(int)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for pw, pv in dp.copy().items():
        if pw + w <= W:
            dp[pw + w] = max(dp[pw + w], pv + v)

print(max(dp.values()))

Solution (Python):
n, w = map(int, input().split())
wd = {}
minw, v = map(int, input().split())
wd[minw] = [v]
wd[minw+1] = []
wd[minw+2] = []
wd[minw+3] = []
for _  in range(n-1):
  _w, v = map(int, input().split())
  wd[_w].append(v)

for k, v in wd.items():
  wd[k] = list(sorted(v))[::-1]

maxw = 0
for i in range(w // minw + 1):
  for j in range((w - minw * i) // (minw + 1) + 1):
    for k in range((w - minw * i - (minw + 1) * j) // (minw + 2) + 1):
      l = (w - minw * i - (minw + 1) * j - (minw + 2) * k) // (minw + 3)
      tmp = sum(wd[minw][:i]) + sum(wd[minw+1][:j]) + sum(wd[minw+2][:k]) + sum(wd[minw+3][:l])
      if tmp > maxw:
        maxw = tmp
print(maxw)

Solution (Python):
n, w = map(int, input().split())
di = dict()
m = 0
for _ in range(n):
  x,y = map(int, input().split())
  if x not in di:
    di[x] = []
  di[x].append(y)
for i in di:
  di[i].sort(reverse=True)
a = min(di.keys())
b,c,d = a+1,a+2,a+3
for i in b,c,d:
  if i not in di:
    di[i] = []
for i in range(len(di[a])+1):
  for j in range(len(di[b])+1):
    for k in range(len(di[c])+1):
      for l in range(len(di[d])+1):
        if i*a + j*b + k*c + l*d <= w:
          m = max(m, sum(di[a][:i] + di[b][:j] + di[c][:k] + di[d][:l]))
print(m)

Solution (Python):
n,w = map(int, input().split())
w4 = [[] for i in range(4)]
w1 = None
for i in range(n):
    ws, vs = map(int,input().split())
    if i == 0:
        w1 = ws
    ws -= w1
    w4[ws].append(vs)

for i in range(4):
    w4[i].sort(reverse=True)
    tmp = [0]
    for j in w4[i]:
        tmp.append(tmp[-1]+j)
    w4[i] = tmp
ans = 0
for i in range(len(w4[0])):
    for j in range(len(w4[1])):
        for k in range(len(w4[2])):
            for l in range(len(w4[3])):
                if w >= w1*(i+j+k+l) + j + 2*k + 3*l:
                    ans = max(ans, w4[0][i]+w4[1][j]+w4[2][k]+w4[3][l])
print(ans)

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

dp = [[[-1]*4*n for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
w1 = None
for i in range(n):
    ws, vs = map(int, input().split())
    if i == 0:
        w1 = ws
    ws -= w1
    for j in range(i+2):
        for k in range(4*n):
            if j-1 >= 0 and k-ws >= 0 and dp[i][j-1][k-ws] >= 0:
                dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-ws]+vs)
            else:
                dp[i+1][j][k] = dp[i][j][k]

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