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

MINW = WV[0][0]

W0,W1,W2,W3 = [],[],[],[]
for w,v in WV:
    if w == MINW: W0.append(v)
    elif w == MINW + 1: W1.append(v)
    elif w == MINW + 2: W2.append(v)
    elif w == MINW + 3: W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)

W0 = [0] + W0
W1 = [0] + W1
W2 = [0] + W2
W3 = [0] + W3

from itertools import accumulate

W0 = list(accumulate(W0))
W1 = list(accumulate(W1))
W2 = list(accumulate(W2))
W3 = list(accumulate(W3))

ans = 0
for cnt0 in range(len(W0)):
    for cnt1 in range(len(W1)):
        for cnt2 in range(len(W2)):
            for cnt3 in range(len(W3)):
                SUMW = cnt0 * MINW
                SUMW += cnt1 * (MINW + 1)
                SUMW += cnt2 * (MINW + 2)
                SUMW += cnt3 * (MINW + 3)

                if SUMW <= W:
                    SUMV = W0[cnt0]
                    SUMV += W1[cnt1]
                    SUMV += W2[cnt2]
                    SUMV += W3[cnt3]
                    ans = max(ans, SUMV)

print(ans)

Solution (Python):
from itertools import accumulate
n,W,*L=map(int,open(0).read().split())
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	if m*i>W:
		continue
	for j in range(lim[1]):
		if m*i+(m+1)*j>W:
			continue
		for k in range(lim[2]):
			if m*i+(m+1)*j+(m+2)*k>W:
				continue
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)

Solution (Python):
N,W = map(int,input().split())
list0 = []
list1 = []
list2 = []
list3 = []
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    if w == w1:
        list0.append(v)
    if w == w1 + 1:
        list1.append(v)
    if w == w1 + 2:
        list2.append(v)
    if w == w1 + 3:
        list3.append(v)
list0.sort(reverse = True)
list1.sort(reverse = True)
list2.sort(reverse = True)
list3.sort(reverse = True)
l0 = len(list0)
l1 = len(list1)
l2 = len(list2)
l3 = len(list3)
ans = 0
for i in range(min(l0,W//w1)+1):
    curw1 = W - w1*i
    for j in range(min(l1,curw1//(w1+1))+1):
        curw2 = curw1-(w1+1)*j
        for k in range(min(l2,curw2//(w1+2))+1):
            curw3 = curw2- (w1+2)*k
            l = min(l3,curw3//(w1+3))
            value = 0
            for a in range(i):
                value += list0[a]
            for a in range(j):
                value += list1[a]
            for a in range(k):
                value += list2[a]
            for a in range(l):
                value += list3[a]
            ans = max(ans,value)
print(ans)

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

N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
w1 = wv[0][0]
dp = [[0] * 301 for _ in range(N+1)]
for w, v in wv:
    w -= w1
    for i in range(1, N+1)[::-1]:
        for j in range(w, 301):
            dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
ans = 0
for i in range(N+1):
    w = W - w1*i
    if w < 0:
        break
    ans = max(ans, dp[i][min(300, W-w1*i)])
print(ans)

Solution (Python):
from itertools import accumulate
n,W,*L=map(int,open(0).read().split())
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	for j in range(lim[1]):
		for k in range(lim[2]):
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)

Solution (Python):
N, W = map(int, input().split())
WV = [tuple(map(int, input().split())) for _ in range(N)]
R = 3 * N + 10
INF = 10**18

w0 = WV[0][0]

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

for w, v in WV:
    k = w - w0
    for n in range(N)[::-1]:
        for r in range(R)[::-1]:
            if r + k < R and dp[n + 1][r + k] < dp[n][r] + v:
                dp[n + 1][r + k] = dp[n][r] + v

ans = 0
for n in range(N + 1):
    for r in range(R):
        w = n * w0 + r
        if w <= W and dp[n][r] > ans:
            ans = dp[n][r]
print(ans)

Solution (Python):
N,W = list(map(int, input().split()))
w_0 = []
w_1 = []
w_2 = []
w_3 = []
v = []
w = 0
w_count = [0]*4
for _ in range(N):
    a,b = list(map(int, input().split()))
    if w == 0:
        w = a
        w_0.append(b)
    else:
        if a == w:
            w_0.append(b)
        elif a == w+1:
            w_1.append(b)
        elif a == w+2:
            w_2.append(b)
        elif a == w+3:
            w_3.append(b)
    w_count[a-w] += 1

w_0.sort(reverse=True)
w_1.sort(reverse=True)
w_2.sort(reverse=True)
w_3.sort(reverse=True)
ans = 0

for i in range(w_count[0]+1):
    for j in range(w_count[1]+1):
        for k in range(w_count[2]+1):
            for l in range(w_count[3]+1):
                if W >= w * i + (w+1) * j + (w+2) * k + (w+3) * l:
                  
                    S = sum(w_0[:i])+sum(w_1[:j])+sum(w_2[:k])+sum(w_3[:l])
                    ans = max(ans,S)

print(ans)

Solution (Python):


from collections import defaultdict
from copy import copy

def main():
    n, wmax = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for i in range(n):
        w, v = map(int, input().split())
        dppre = copy(dp)
        for y in dppre:
            dp[y + w] = max(dp[y + w], dppre[y] + v)
    res = 0
    for y, z in dp.items():
        if y <= wmax:
            res = max(res, z)
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque
import copy

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

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Solution (Python):
import sys
from collections import deque
import copy
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Solution (Python):
import sys
from collections import *
import copy
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Solution (Python):
from itertools import accumulate
w=[[] for _ in range(4)]
N,W=map(int,input().split())
w1,v1=map(int,input().split())
w[0].append(v1)
for _ in range(N-1):
    wi,vi=map(int,input().split())
    w[wi-w1].append(vi)
for i in range(4):
    w[i].sort(reverse=True)
    w[i]=list(accumulate(w[i]))
ans=0
for i in range(len(w[0])+1):
    for j in range(len(w[1])+1):
        for k in range(len(w[2])+1):
            for l in range(len(w[3])+1):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    su=0
                    if i>0:
                        su+=w[0][i-1]
                    if j>0:
                        su+=w[1][j-1]
                    if k>0:
                        su+=w[2][k-1]
                    if l>0:
                        su+=w[3][l-1]
                    ans=max(ans,su)
print(ans)

Solution (Python):
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)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""

dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            if dp[i][n][j] == -1:continue
            dp[i+1][n+1][j+w] = max(dp[i][n][j] + v, dp[i][n][j+w])
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])

ans = 0
for i,a in enumerate(dp[N]):
    w = W - i*ws[0]
    if w >= 0:
        ans = max(ans,max(a[:w+1]))
print(ans)

Solution (Python):
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)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[-1]*(3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):    
    dp[i+1][:] = dp[i][:]
    for j in range(len(dp[i])):
        if dp[i][j] == -1:continue
        dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
    



dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    
    for n in range(N):
        
        for j in range(N):
            if dp[i][n][j] == -1:continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    


    
anss = dp[N]
a = 0
for i,ans in enumerate(anss):
    w = W - i*ws[0]
    if w >= 0:
        a = max(a,max(ans[:w+1]))
print(a)

Solution (Python):
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)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+10) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            if dp[i][n][j] == -1: continue
            if j + (n+1)*ws[0] + w <= W:
                dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)

ans= 0
for i,As in enumerate(dp[N]):
    w = min(W - i*ws[0], sum(ws_m))
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Solution (Python):
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)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+10) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            
            if j + (n+1)*ws[0] + w <= W:
                dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)

ans= 0
for i,As in enumerate(dp[N]):
    w = min(W - i*ws[0], sum(ws_m))
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Solution (Python):
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)
ws_m = [w-ws[0] for w in ws]

sum_ws_m = sum(ws_m)

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[0]*(3*N+10) for i in range(N+10)] for j in range(N+10)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            
            
            if ws[0]*(n+1)+j+w <= W:
                dp[i+1][n+1][j+w] = max(dp[i+1][n+1][j+w], dp[i][n][j]+v)
            
                
            dp[i+1][n][j] = max( dp[i+1][n][j], dp[i][n][j] )
            
            
            
            
            
        
ans= 0
for i,As in enumerate(dp[N]):
    w = min( W - i*ws[0], sum_ws_m )
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=[]
for w,v in WV:
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1:
            lst.append([w1+w,v1+v])
    lst.append([w,v])

    lst=sorted(lst,key=lambda x:x[0],reverse=True)
    while lst and lst[-1][0]==0:
        lst.pop()

    w,v=lst[-1]
    for i in range(len(lst)-1)[::-1]:
        w1,v1=lst[i]
        if v1<=v:
            lst[i][0]=0
            lst[i][1]=0
        else:
            v=v1
    
print(max([v for w,v in lst if w<=W]))

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

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

for j in range(0,N+1):
    for k in range(0,3*N+1):
        weight=w[0]*j+k
        if weight>W:
            dp[0][j][k]=-1
        else:
            dp[0][j][k]=0

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

if dp[N][0][0]==-1:
    print(0)
else:
    print(dp[N][0][0])

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import sys
input = sys.stdin.readline
from heapq import*


N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]
dp=[[0 for i in range(301*(N+1))] for n in range(N)]
Z=WV[0][0]

for i in range(N):
    WV[i][0]-=Z
for n in range(N):
    for i in range(len(dp[0])):
        w,v=WV[n]
        if n==0:
            dp[n][w+301]=v
        else:
            dp[n][w+301]=max(dp[n-1][w+301],v)
            if i>=w+301:
                if dp[n-1][i-(w+301)]:
                    dp[n][i]=max(dp[n-1][i-(w+301)]+v,dp[n-1][i])
                else:
                    dp[n][i]=dp[n-1][i]
            else:
                dp[n][i]=dp[n-1][i]


print(max([max([dp[n][i] for i in range(len(dp[0])) if W>=i//301*Z+i%301]) for n in range(N)]))

Solution (Python):
n,weight=map(int,input().split())
ans=0
bag=[[] for i in range(4)]
W,V=map(int,input().split());bag[0].append((W,V))
for i in range(n-1):
    w,v=map(int,input().split())
    bag[w-W].append((w,v))
for i in range(4):
    bag[i].sort(key=lambda x:x[1],reverse=True)
valuesum=[[0 for i in range(len(bag[j])+1)] for j in range(4)]
for i in range(4):
    for j in range(len(bag[i])):
        valuesum[i][j+1]=valuesum[i][j]+bag[i][j][1]
for i in range(len(bag[0])+1):
    for j in range(len(bag[1])+1):
        for k in range(len(bag[2])+1):
            for l in range(len(bag[3])+1):
                if i*W+j*(W+1)+k*(W+2)+l*(W+3)>weight:continue
                if valuesum[0][i]+valuesum[1][j]+valuesum[2][k]+valuesum[3][l]>ans:
                    ans=valuesum[0][i]+valuesum[1][j]+valuesum[2][k]+valuesum[3][l]
print(ans)

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

def main():
    N,W = map(int,input().split())
    use = [[] for _ in range(4)]
    wc,v = map(int,input().split())
    use[0].append(v)
    for _ in range(N-1):
        w,v = map(int,input().split())
        use[w-wc].append(v)

    for i in range(4):
        use[i].sort(reverse = True)
        use[i] = [0]+use[i]
        l = len(use[i])
        for x in range(l-1):
            use[i][x+1] += use[i][x]

    ans = 0
    for i in range(min(len(use[3]),W//(wc+3)+1)):
        Wa = W-(wc+3)*i
        for j in range(min(len(use[2]),Wa//(wc+2)+1)):
            Wb = Wa-(wc+2)*j
            for k in range(min(len(use[1]),Wb//(wc+1)+1)):
                Wc = Wb-(wc+1)*k
                l = min(len(use[0])-1,Wc//wc)
                point = use[0][l]+use[1][k]+use[2][j]+use[3][i]
                ans = max(point,ans)
                
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,W=MI()
    WV=LLIN(N)
    W0 = WV[0][0]
    for i,(w,v) in enumerate(WV):
        WV[i][0] = w-W0
    WV.sort(key=lambda x: x[1], reverse=True)
    cumsum = [0]*N
    for i,(w,v) in enumerate(WV):
        cumsum[i]=cumsum[i-1]+v

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

    ans = 0 
    for k in range(1,N+1):
        W_k = W-W0*k
        if W_k>=N*3:
            ans = max(ans, cumsum[k-1])
            continue
        if W_k<0:
            break   
        ans = max(ans, dp[k][W_k])
    print(ans)



if __name__ == '__main__':
    main()

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

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

MINW = WV[0][0]


W0 = sorted([0] + [v for w,v in WV if w == MINW])
W1 = sorted([0] + [v for w,v in WV if w == MINW+1])
W2 = sorted([0] + [v for w,v in WV if w == MINW+2])
W3 = sorted([0] + [v for w,v in WV if w == MINW+3])


W0 = tuple(accumulate(W0))
W1 = tuple(accumulate(W1))
W2 = tuple(accumulate(W2))
W3 = tuple(accumulate(W3))

ans = 0
for w0 in range(len(W0)):
    for w1 in range(len(W1)):
        for w2 in range(len(W2)):
            for w3 in range(len(W3)):
                
                tmp = (len(W0) - (w0 + 1)) * MINW
                tmp += (len(W1) - (w1 + 1)) * (MINW+1)
                tmp += (len(W2) - (w2 + 1)) * (MINW+2)
                tmp += (len(W3) - (w3 + 1)) * (MINW+3)

                
                if tmp <= W:
                    
                    tmp = W0[-1] - W0[w0]
                    tmp += W1[-1] - W1[w1]
                    tmp += W2[-1] - W2[w2]
                    tmp += W3[-1] - W3[w3]
                    ans = max(ans, tmp)

print(ans)

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

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

MINW = WV[0][0]

W0 = sorted([0] + [v for w,v in WV if w == MINW])
W1 = sorted([0] + [v for w,v in WV if w == MINW+1])
W2 = sorted([0] + [v for w,v in WV if w == MINW+2])
W3 = sorted([0] + [v for w,v in WV if w == MINW+3])

W0 = tuple(accumulate(W0))
W1 = tuple(accumulate(W1))
W2 = tuple(accumulate(W2))
W3 = tuple(accumulate(W3))

ans = 0
for w0 in range(len(W0)):
    for w1 in range(len(W1)):
        for w2 in range(len(W2)):
            for w3 in range(len(W3)):
                tmp = (len(W0) - (w0 + 1)) * MINW
                tmp += (len(W1) - (w1 + 1)) * (MINW+1)
                tmp += (len(W2) - (w2 + 1)) * (MINW+2)
                tmp += (len(W3) - (w3 + 1)) * (MINW+3)

                if tmp <= W:
                    tmp = W0[-1] - W0[w0]
                    tmp += W1[-1] - W1[w1]
                    tmp += W2[-1] - W2[w2]
                    tmp += W3[-1] - W3[w3]
                    ans = max(ans, tmp)

print(ans)

Solution (Python):
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w_base = WV[0][0]
    WV[0][0] = 0
    V = {i: [0] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    ans = 0
    from itertools import product
    for p in product(range(len(V[0])), range(len(V[1])),
                     range(len(V[2])), range(len(V[3]))):
        w_cur = w_base*p[0] + (w_base+1)*p[1] + \
            (w_base+2)*p[2] + (w_base+3)*p[3]
        if W < w_cur:
            continue
        ans = max(ans, sum(sum(V[i][:min(p[i], len(V[i]))]) for i in range(4)))
    print(ans)


if __name__ == '__main__':
    main()