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 sys
input = sys.stdin.readline
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    w_sub-=w0
    x[w_sub].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(reverse=True)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=10000000000
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
x_sub=[[v_sub],[],[],[]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x_sub[z].append(v_sub)
for i in range(4):
    x_sub[i].sort(key=lambda x:-x)

x=[[0],[0],[0],[0]]
for i in range(4):
    for j in x_sub[i]:
        k=j+x[i][-1]
        x[i].append(k)


ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
from operator import itemgetter
n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=itemgetter(1),reverse=True)
wv.sort(key=itemgetter(0))

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    m=min(d//w0,l0-1)
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][m]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        if w-i*(w0+3)-j*(w0+2)>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    d=w-i*(w0+3)
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        for k in range(l1):
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
                ma=max(ma,ma_sub)

print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        for k in range(l1):
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
            ma=max(ma,ma_sub)
print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        for k in range(l1):
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
            ma=max(ma,ma_sub)
print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
for i in range(len(x[3])):
    for j in range(len(x[2])):
        for k in range(len(x[1])):
            
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
            ma=max(ma,ma_sub)
print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
for i in range(len(x[3])):
    for j in range(len(x[2])):
        for k in range(len(x[1])):
            for l in range(len(x[0])):
                if i*(w0+3)+j*(w0+2)+k*(w0+1)+l*w0<=w:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][l]
                    ma=max(ma,ma_sub)
                else:
                    break
print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            for l in range(len(x[3])):
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub=x[0][i]+x[1][j]+x[2][k]+x[3][l]
                    ma=max(ma,ma_sub)
                else:
                    break
print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            for l in range(len(x[3])):
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub=0
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                    ma=max(ma,ma_sub)
                else:
                    break
print(ma)

Solution (Python):
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)

ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            for l in range(len(x[3])):
                ma_sub=0
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                ma=max(ma,ma_sub)
print(ma)

Solution (Python):
from collections import defaultdict

N, W = map(int, input().split())

data_list = []
for i in range(N):
    w, v = map(int, input().split())
    data_list.append((w, v))
    
data = defaultdict(int)
data[0] = 0
for w, v in data_list:
    for cw, cv in list(data.items()):
        if cw + w <= W:
            data[cw+w] = max(data[cw+w], cv+v)
            
print(max(data.values()))

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n,W = inpm()
    v = [[] for _ in range(4)]
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        v[ wv[0]-w0 ].append(wv[1])
    for i in range(4):
        v[i] = sorted(v[i])
        v[i].reverse()
        vv = [0 for _ in range(len(v[i])+1)]
        for j in range(len(v[i])):
            vv[j+1] = vv[j] + v[i][j]
        v[i] = vv
    ans = 0
    for n1 in range(len(v[0])):
        for n2 in range(len(v[1])):
            for n3 in range(len(v[2])):
                for n4 in range(len(v[3])):
                    if W < w0*(n1+n2+n3+n4) + n2 + n3*2 + n4*3:
                        continue
                    ans = max(ans,v[0][n1]+v[1][n2]+v[2][n3]+v[3][n4])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product, accumulate

N, W = map(int, input().split())
v0, v1, v2, v3 = [None], [], [], []
w0, v0[0] = map(int, input().split())
for i in range(1, N):
    w, v = map(int, input().split())
    if w - w0 == 0:
        v0.append(v)
    elif w - w0 == 1:
        v1.append(v)
    elif w - w0 == 2:
        v2.append(v)
    else:
        v3.append(v)

v0 = sorted(v0, reverse=True)
v1 = sorted(v1, reverse=True)
v2 = sorted(v2, reverse=True)
v3 = sorted(v3, reverse=True)

av0 = [0] + list(accumulate(v0))
av1 = [0] + list(accumulate(v1))
av2 = [0] + list(accumulate(v2))
av3 = [0] + list(accumulate(v3))

ans = 0
for i, j, k, l in product(range(len(v0) + 1), range(len(v1) + 1),
                          range(len(v2) + 1), range(len(v3) + 1)):
    v = av0[i] + av1[j] + av2[k] + av3[l]
    w = w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l
    if w <= W:
        ans = max(v, ans)
print(ans)

Solution (Python):


import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, W = MAP()
WV = []
for i in range(N):
    w, v = MAP()
    WV.append((w, v))

dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = WV[i]
    for k in dp[i].keys():
        dp[i+1][k] = max(dp[i+1][k], dp[i][k])
        if k+w <= W:
            dp[i+1][k+w] = max(dp[i+1][k+w], dp[i][k] + v)
print(max(dp[N].values()))

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

INF = 10 ** 10
w0 = INF
for w, v in wv:
  w0 = min(w0, w)

for i in range(N):
  wv[i][0] -= w0


U = [[] for _ in range(4)]
for w, v in wv:
  U[w].append(v)
  
for i in range(4):
  U[i].sort(reverse = True)


S = [[0] for _ in range(4)]
for i in range(4):
  for u in U[i]:
    S[i].append(S[i][-1] + u)


answer = []
for i0 in range(len(S[0])):
  for i1 in range(len(S[1])):
    for i2 in range(len(S[2])):
      for i3 in range(len(S[3])):
        if i1 + i2 * 2 + i3 * 3 + (i0 + i1 + i2 + i3) * w0 <= W:
          answer.append(S[0][i0] + S[1][i1] + S[2][i2] + S[3][i3])
print(max(answer))

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

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

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

S = []
for vl in V:
    vl.sort(reverse=True)
    s = [0]
    for v in vl:
        s.append(s[-1]+v)
    S.append(s)

ans = 0
for n0, s0 in enumerate(S[0]):
    for n1, s1 in enumerate(S[1]):
        for n2, s2 in enumerate(S[2]):
            for n3, s3 in enumerate(S[3]):
                if n0*w1 + n1*(w1+1) + n2*(w1+2) + n3*(w1+3)<=W:
                    ans = max(ans, s0+s1+s2+s3)
print(ans)

Solution (Python):
import sys
from itertools import accumulate

n, W, *wv = map(int, sys.stdin.read().split())
wv = list(zip(*[iter(wv)] * 2))

def main():
    wv.sort(key=lambda x: x[0])
    min_w = wv[0][0]

    items = [[] for _ in range(4)]
    
    for w, v in wv:
        items[w-min_w].append(v)
    
    for i in range(4):
        items[i].sort(reverse=True)
        items[i].insert(0, 0)
        items[i] = list(accumulate(items[i]))

    res = 0
    s0 = items[0]
    s1 = items[1]
    s2 = items[2]
    s3 = items[3]
    for i in range(len(s0)):
        v0 = s0[i]
        for j in range(len(s1)):
            v1 = s1[j]
            for k in range(len(s2)):
                v2 = s2[k]
                for l in range(len(s3)):
                    v3 = s3[l]
                    if (j + 2*k + 3*l) + min_w * (i+j+k+l) <= W:
                        res = max(res, v0+v1+v2+v3)

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import itertools
n, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
b = []
c = []
d= []
e= []
ans=0

for i in range(n):
    if a[i][0] == a[0][0]:
        b.append(a[i][1])
    elif a[i][0] == a[0][0]+1:
        c.append(a[i][1])
    elif a[i][0] == a[0][0]+2:
        d.append(a[i][1])
    else:
        e.append(a[i][1])

b.sort()
b.reverse()
c.sort()
c.reverse()
d.sort()
d.reverse()
e.sort()
e.reverse()

b = list(itertools.accumulate(b))
c = list(itertools.accumulate(c))
d = list(itertools.accumulate(d))
e = list(itertools.accumulate(e))
b.append(0)
c.append(0)
d.append(0)
e.append(0)


for i in range(len(b)):
    for j in range(len(c)):
        for k in range(len(d)):
            if a[0][0]*i+(a[0][0] +1)*j+(a[0][0] +2)*k>w:
                break
            else:
                x=(w-(a[0][0]*i+(a[0][0] +1)*j+(a[0][0] +2)*k))//(a[0][0]+3)
                ans=max(ans,b[i-1]+c[j-1]+d[k-1]+e[min(x-1,len(e)-1)])
print(ans)

Solution (Python):
import sys

n, W = map(int, sys.stdin.readline().split())
wv = map(int, sys.stdin.read().split())

wv = sorted(zip(*[wv] * 2))
min_w = wv[0][0]
W2 = 4 * n

def main():
    dp = [[[0] * (W2 + 1) for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(n):
        w, v = wv[i]
        w -= min_w - 1
        for j in range(1, i+2):
            for k in range(W2 + 1):
                if k + (min_w - 1) * j > W:
                    break
                dp[i+1][j][k] = dp[i][j][k]
                if k >= w:
                    dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-w] + v)

    res = 0
    for j in dp[n]:
        res = max(res, max(j))

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W//A[0][0] > 100:
        print(sum(list(zip(*A))[1]))
        exit()
    if W%A[0][0] >= 300:
        W = W//A[0][0]*300+299
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

DP = [[0 for i in range(31000)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,31000):
        DP[i][j] = max(DP[i][j],DP[i-1][j],DP[i][j-1])
        if j-A[i-1][0]>=0:
            DP[i][j] = max(DP[i][j],DP[i-1][j-A[i-1][0]]+A[i-1][1])            

print(DP[N][W])

Solution (Python):
import sys
from itertools import accumulate, product
from operator import itemgetter
read = sys.stdin.read

N, W, *wv = map(int, read().split())
w1 = wv[0]
V = [[0] for _ in range(4)]

for w, v in sorted(zip(*[iter(wv)] * 2), key=itemgetter(1), reverse=True):
    V[w - w1].append(v)


V = list(map(list, map(accumulate, V)))
n = [len(V[i]) for i in range(4)]
answer = 0
for a, b, c in product(range(n[0]), range(n[1]), range(n[2])):
    tmp = b + c * 2 + (a + b + c) * w1
    if tmp > W:
        continue

    d = min(n[3] - 1, (W - tmp) // (w1 + 3))
    v = V[0][a] + V[1][b] + V[2][c] + V[3][d]
    if v > answer:
        answer = v

print(answer)

Solution (Python):
import sys
from itertools import accumulate, product
from operator import itemgetter
read = sys.stdin.read

N, W, *wv = map(int, read().split())
w1 = wv[0]
V = [[0] for _ in range(4)]

for w, v in sorted(zip(*[iter(wv)] * 2), key=itemgetter(1), reverse=True):
    V[w - w1].append(v)


V = list(map(list, map(accumulate, V)))
n = [len(V[i]) for i in range(4)]
answer = 0
for a, b, c, d in product(range(n[0]), range(n[1]), range(n[2]), range(n[3])):
    if b + c * 2 + d * 3 + (a + b + c + d) * w1 > W:
        continue

    v = V[0][a] + V[1][b] + V[2][c] + V[3][d]
    if v > answer:
        answer = v

print(answer)

Solution (Python):
N, W = map(int, input().split())
w0, v0 = map(int, input().split())
X = [[] for _ in range(4)]
X[0].append(v0)
for _ in range(N-1):
    w, v = map(int, input().split())
    X[w-w0].append(v)

X = [[0] + sorted(x)[::-1] for x in X]
for i in range(4):
    for j in range(1, len(X[i])):
        X[i][j] += X[i][j-1]
ma = 0
for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            l = min(N-i-j-k, (W - (w0 * i + (w0+1) * j + (w0+2) * k)) // (w0+3))
            if l < 0: continue
            if i < len(X[0]) and j < len(X[1]) and k < len(X[2]) and l < len(X[3]):
                ma = max(ma, X[0][i] + X[1][j] + X[2][k] + X[3][l])
print(ma)

Solution (Python):

import sys
from itertools import accumulate
def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    value = {}
    value[w[0]] = []
    value[w[0]+1] = []
    value[w[0]+2] = []
    value[w[0]+3] = []
    accum = {}
    answer = 0

    for i in range(N):
        value[w[i]].append(v[i])

    len0 = len(value[w[0]])
    len1 = len(value[w[0]+1])
    len2 = len(value[w[0]+2])
    len3 = len(value[w[0]+3])

    for i in range(4):
        value[w[0]+i].sort(reverse = True)
        accum[w[0]+i] = [0]+list(accumulate(value[w[0]+i]))

    for i in range(len0+1):
        for j in range(len1+1):
            for k in range(len2+1):
                for l in range(len3+1):
                    if i*w[0]+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) <= W:
                        answer = max(accum[w[0]][i]+accum[w[0]+1][j]+accum[w[0]+2][k]+accum[w[0]+3][l],answer)
    print(answer)
    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()