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):
from itertools import accumulate

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

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

acc = [[0] + list(accumulate(li)) for li in weights]

l3 = len(weights[3])
ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            w_sm = w1 * i + (w1 + 1) * j + (w1 + 2) * k
            if w_sm > W:
                break

            l = min((W - w_sm) // (w1 + 3), l3)
            val = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
            ans = max(ans, val)

print(ans)

Solution (Python):
from itertools import accumulate

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

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

acc = [[0] + list(accumulate(li)) for li in weights]

ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            for l, e4 in enumerate(acc[3]):
                if w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l <= W:
                    ans = max(ans, e1 + e2 + e3 + e4)

print(ans)

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

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = min(W - w1 * j, 3 * n)
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)

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

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

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        
    a=set([0])
    for i in range(N+1):
        for j in range(3*i+1):
            ww=w1*i+j
            if ww>W:
                break
            a.add(ww)
    a=list(a)
    a.sort()
    M=len(a)
    
    
    
    dp=[[-1]*(M) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0]=0
    ans=0
    
    for i in range(N):
        for j in range(M):
            if dp[i][j]!=-1:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j])
                ww=a[j]+w1+w[i]
                if ww<=W:
                    jj=bisect.bisect_left(a,ww)
                    dp[i+1][jj]=max(dp[i+1][jj],dp[i][j]+v[i])
                    ans=max(ans,dp[i+1][jj])
                    
    print(ans)
                    
    
            

main()

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

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

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    w2=[0,0,0,0]
    v2=[[] for _ in range(4)]
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        w2[w[i]]+=1
        v2[w[i]].append(v[i])
        
    for i in range(4):
        v2[i].sort(reverse=True)
        
    s=[[0] for _ in range(4)]
    for i in range(4):
        for j in range(len(v2[i])):
            s[i].append(s[i][-1]+v2[i][j])
     
    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])):
                    ww=b+2*c+3*d+w1*(a+b+c+d)
                    if ww<=W:
                        temp=s[0][a]+s[1][b]+s[2][c]+s[3][d]
                        ans=max(ans,temp)
                        
    print(ans)
                        
        
    

main()

Solution (Python):


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

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base+1<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)
    

print(ans)

Solution (Python):
import sys

input = sys.stdin.readline


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


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    import bisect

    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    init_w = I[0][0]
    D = {i: [] for i in range(4)}
    S = {i: [0] for i in range(4)}
    for w, v in I:
        bisect.insort(D[w - init_w], -v)

    for i, d in D.items():
        for v in d:
            S[i].append(v + S[i][-1])

    res = 0
    for t0 in range(len(D[0]) + 1):
        for t1 in range(len(D[1]) + 1):
            for t2 in range(len(D[2]) + 1):
                for t3 in range(len(D[3]) + 1):
                    if (t0 + t1 + t2 + t3) * init_w + t1 + 2 * t2 + 3 * t3 > W:
                        continue

                    res = min(res, S[0][t0] + S[1][t1] + S[2][t2] + S[3][t3])
    print(-res)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = min(W - k * w0, 3 * N + 5)
        if r < 0:
            continue
        for i in range(r + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
n,w=map(int,input().split())
wv=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    wv.append([a,b])
    v.append(b)
v.sort(reverse=True)
ans=0
w0=wv[0][0]
wp=3*n+1
dp=[[-1 for jjj in range(n+1)] for iii in range(3*n+1)]
dp[0][0]=0
for i in range(n):
    for jj in range(n-1,-1,-1):
        for k in range(wp-1,-1,-1):
            if dp[k][jj]>=0 and k+wv[i][0]-w0<=wp-1:
                dp[k+wv[i][0]-w0][jj+1]=max(dp[k][jj]+wv[i][1],dp[k+wv[i][0]-w0][jj+1])
for i in range(1,n+1):
    wp=w-w0*i
    if wp<0:
        continue
    elif wp>=3*i:
        ans=max(ans,sum(v[:i]))
    else:
        for j in range(i+1):
            for k in range(wp+1):
                ans=max(dp[k][j],ans)
print(ans)

Solution (Python):
n, w_max = map(int, input().split())
W, V = [], []
Diff_zero = []
Diff_one = []
Diff_two = []
Diff_three = []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
    diff = w - W[0]
    if diff == 0:
        Diff_zero.append(v)
    elif diff == 1:
        Diff_one.append(v)
    elif diff == 2:
        Diff_two.append(v)
    elif diff == 3:
        Diff_three.append(v)

Diff_zero = sorted(Diff_zero, reverse=True)
Diff_one = sorted(Diff_one, reverse=True)
Diff_two = sorted(Diff_two, reverse=True)
Diff_three = sorted(Diff_three, reverse=True)

Diff_zero_ruiseki = [0]
Diff_one_ruiseki = [0]
Diff_two_ruiseki = [0]
Diff_three_ruiseki = [0]

for i in range(len(Diff_zero)):
    Diff_zero_ruiseki.append(Diff_zero[i] + Diff_zero_ruiseki[-1])
for i in range(len(Diff_one)):
    Diff_one_ruiseki.append(Diff_one[i] + Diff_one_ruiseki[-1])
for i in range(len(Diff_two)):
    Diff_two_ruiseki.append(Diff_two[i] + Diff_two_ruiseki[-1])
for i in range(len(Diff_three)):
    Diff_three_ruiseki.append(Diff_three[i] + Diff_three_ruiseki[-1])

value_max = 0
w_zero = W[0]

for i in range(n+1):
    if i > len(Diff_zero):
        continue
    for j in range(n+1):
        if j > len(Diff_one):
            continue
        for k in range(n+1):
            if k > len(Diff_two):
                continue
            for l in range(n+1):
                if l > len(Diff_three):
                    continue
                if w_zero*i + (w_zero+1)*j + (w_zero+2)*k + (w_zero+3)*l > w_max:
                    continue
                if i + j + k + l > n:
                    continue

                value = Diff_zero_ruiseki[i] + Diff_one_ruiseki[j] + Diff_two_ruiseki[k] + Diff_three_ruiseki[l]
                value_max = max(value, value_max)

print(value_max)

Solution (Python):

n,u = map(int,input().split())
wv = [[] for _ in range(4)]
for i in range(n):
  w,v = map(int,input().split())
  if i == 0:
    w0 = w
  wv[w-w0].append(v)

z = []
for d in range(4):
  wv[d].sort(reverse=True)
  z.append(len(wv[d]))
cum = []
for d in range(4):
  tmp = [0]
  for x in wv[d]:
    tmp.append(tmp[-1]+x)
  cum.append(tmp)


can = [0]
for i0 in range(z[0]+1):
  y0 = cum[0][i0]
  for i1 in range(z[1]+1):
    y1 = cum[1][i1]
    for i2 in range(z[2]+1):
      y2 = cum[2][i2]
      for i3 in range(z[3]+1):
        y3 = cum[3][i3]
        if i0*w0 + i1*(w0+1) + i2*(w0+2) + i3*(w0+3) <= u:
          can.append(y0+y1+y2+y3)

print(max(can))

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

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
w0 = w[0]
for i in range(N):
    w[i] -= w0
s = sum(w)
dp = [[-1] * (s+1) for _ in range(N+1)]
dp[0] = [0] * (s+1)
for n in range(N):
    for i in range(N)[::-1]:
        for j in range(s-w[n]+1)[::-1]:
            if dp[i][j] == -1:
                continue
            dp[i+1][j+w[n]] = max(dp[i+1][j+w[n]], dp[i][j] + v[n])
ans = 0
for i in range(N+1):
    if W - w0 * i >= 0:
        ans = max(ans, dp[i][min(s, W-w0*i)])
print(ans)

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

V0 = []
V1 = []
V2 = []
V3 = []

for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        V0.append(v)
    else:
        if w == w1:
            V0.append(v)
        elif w == w1+1:
            V1.append(v)
        elif w == w1+2:
            V2.append(v)
        else:
            V3.append(v)

V0.sort(reverse=True)
V1.sort(reverse=True)
V2.sort(reverse=True)
V3.sort(reverse=True)

from itertools import accumulate
CV0 = [0] + V0
CV0 = list(accumulate(CV0))
CV1 = [0] + V1
CV1 = list(accumulate(CV1))
CV2 = [0] + V2
CV2 = list(accumulate(CV2))
CV3 = [0] + V3
CV3 = list(accumulate(CV3))

ans = -float('inf')
for a in range(len(V0)+1):
    for b in range(len(V1)+1):
        for c in range(len(V2)+1):
            for d in range(len(V3)+1):
                if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
                    sum_v = CV0[a]+CV1[b]+CV2[c]+CV3[d]
                    ans = max(ans, sum_v)

print(ans)

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

V0 = []
V1 = []
V2 = []
V3 = []

for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        V0.append(v)
    else:
        if w == w1:
            V0.append(v)
        elif w == w1+1:
            V1.append(v)
        elif w == w1+2:
            V2.append(v)
        else:
            V3.append(v)

V0.sort(reverse=True)
V1.sort(reverse=True)
V2.sort(reverse=True)
V3.sort(reverse=True)

from itertools import accumulate
CV0 = [0] + V0
CV0 = list(accumulate(CV0))
CV1 = [0] + V1
CV1 = list(accumulate(CV1))
CV2 = [0] + V2
CV2 = list(accumulate(CV2))
CV3 = [0] + V3
CV3 = list(accumulate(CV3))

ans = -float('inf')
for a in range(len(V0)+1):
    for b in range(len(V1)+1):
        for c in range(len(V2)+1):
            for d in range(len(V3)+1):
                if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
                    sum_v = CV0[a]+CV1[b]+CV2[c]+CV3[d]
                    ans = max(ans, sum_v)

print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,w = m()

po = [[] for i in range(4)]
pr = [[0] for i in range(4)]

for i in range(n):
    a,b = m()
    if i == 0:
        coo = a
        po[0].append(b)
    else:
        kkk = a - coo
        po[kkk].append(b)

for i in range(4):
    po[i].sort(reverse = True)
    for ii in range(len(po[i])):
        pr[i].append(pr[i][-1] + po[i][ii])

co = 0
su = 0
for i in range(len(po[0]) + 1):
    for ii in range(len(po[1]) + 1):
        for iii in range(len(po[2]) + 1):
            for iiii in range(len(po[3]) + 1):
                if (i * coo + ii * (coo + 1) + iii * (coo + 2) + iiii * (coo + 3)) <= w:
                    su = max(su,pr[0][i]+pr[1][ii]+pr[2][iii]+pr[3][iiii])

print(su)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
N,W = map(int,readline().split())
w,v = map(int,readline().split())
tmp = w
lst1 = [1,0,0,0]
v0 = [v]
v1 = []
v2 = []
v3 = []
for i in range(N-1):
    w,v = map(int,readline().split())
    if w == tmp:
        lst1[0] += 1
        v0.append(v)
    elif w == tmp+1:
        lst1[1] += 1
        v1.append(v)
    elif w == tmp+2:
        lst1[2] += 1
        v2.append(v)
    else:
        lst1[3] += 1
        v3.append(v)
v0.sort(reverse=True)
for i in range(1,lst1[0]):
    v0[i] += v0[i-1]
v1.sort(reverse=True)
for i in range(1,lst1[1]):
    v1[i] += v1[i-1]
v2.sort(reverse=True)
for i in range(1,lst1[2]):
    v2[i] += v2[i-1]
v3.sort(reverse=True)
for i in range(1,lst1[3]):
    v3[i] += v3[i-1]

ans = 0
for i in range(lst1[0]+1):
    for j in range(lst1[1]+1):
        for k in range(lst1[2]+1):
            for l in range(lst1[3]+1):
                res = i*tmp+j*(tmp+1)+k*(tmp+2)+l*(tmp+3)
                if W >= res:
                    res2 = 0
                    if i != 0:
                        res2 += v0[i-1]
                    if j != 0:
                        res2 += v1[j-1]
                    if k != 0:
                        res2 += v2[k-1]
                    if l != 0:
                        res2 += v3[l-1]


                    ans = max(ans,res2)

print(ans)

Solution (Python):
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(M+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,0,-1):
    for j in range(M,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M+1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)

Solution (Python):
import numpy as np
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
ls = np.array(ls)
w1 = ls[0][0]
ls[:,0] -= w1

M = 3*N
dp = np.full((N+1,M+1), -float('inf'))
dp[0][0] = 0

for i in range(N):
  w, v = ls[i]
  dp[1:,w:] = np.maximum(dp[1:,w:], dp[:N,:M-w+1]+v)
  
ans = 0
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M+1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(int(ans))

Solution (Python):
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(M+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,0,-1):
    for j in range(M,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M+1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)

Solution (Python):
from itertools import accumulate
n,w=map(int, input().split())
items = {}
for _ in range(n):
    u,v = map(int, input().split())
    if u not in items:
        items[u] = []
    items[u].append(v)
cost = 0
acc = []
minkey = min(items.keys())
for i in range(4):
    if minkey + i in items:
        items[minkey + i].sort(reverse=True)
        acc.append([0] + list(accumulate(items[minkey + i])))
    else:
        acc.append([0])

ans = 0
for i in range(len(acc[0])):
    a = (i) * minkey
    if w < a:
        continue
    for j in range(len(acc[1])):
        b = (j) * (minkey+1)
        if w < a + b:
            continue
        for k in range(len(acc[2])):
            c = (k) * (minkey+2)
            if w < a + b + c:
                continue
            for l in range(len(acc[3])):
                d = (l) * (minkey+3)
                if w < a + b + c + d:
                    continue
                cost = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
                if cost > ans :
                    ans = cost

print(ans)

Solution (Python):
from collections import defaultdict


def to_cumsum(arr):
    arr.sort(reverse=True)
    cumsum = 0
    new = [0] * (len(arr) + 1)
    for i, e in enumerate(arr):
        cumsum += e
        new[i + 1] = cumsum
    return new


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

weights = defaultdict(int)
values = defaultdict(list)
for i in range(N):
    w, v = map(int, input().split())
    weights[w] += 1
    values[w].append(v)
for k, v in values.items():
    values[k] = to_cumsum(v)

w1 = min(weights.keys())
w2 = w1 + 1
w3 = w2 + 1
w4 = w3 + 1
for w in [w1, w2, w3, w4]:
    if len(values[w]) == 0:
        values[w] = [0]

ans = 0
for i1 in range(weights[w1] + 1):
    for i2 in range(weights[w2] + 1):
        for i3 in range(weights[w3] + 1):
            for i4 in range(weights[w4] + 1):
                if w1 * i1 + w2 * i2 + w3 * i3 + w4 * i4 > W:
                    continue
                ans = max(ans, values[w1][i1] + values[w2][i2] + values[w3][i3] + values[w4][i4])
print(ans)

Solution (Python):

N, W = map(int, input().split())
d = {i: [] for i in range(0, 4)}
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    d[w-w0].append(v)

for i in range(4):
    cum = [0]
    d[i].sort(reverse=True)
    for j in d[i]:
        cum.append(cum[-1] + j)
    d[i] = cum[::]


ans = 0
for i in range(len(d[3])):
    v3_sum = d[3][i]
    w3_sum = (w0+3)*i
    for j in range(len(d[2])):
        v2_sum = d[2][j]
        w2_sum = (w0+2)*j
        for k in range(len(d[1])):
            v1_sum = d[1][k]
            w1_sum = (w0+1)*k

            rest = W - (w1_sum + w2_sum + w3_sum)
            if rest < 0:
                continue
            l = min(rest // w0, len(d[0])-1)
            v0_sum = d[0][l]
 
            ans = max(ans, v0_sum + v1_sum + v2_sum + v3_sum)

print(ans)

Solution (Python):
import itertools
n, W = list(map(int, input().split()))
data = [[] for i in range(4)]
base = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        base = w
    data[w-base].append(v)
for i in range(4):
    data[i].sort(reverse=True)
    data[i] = list(itertools.accumulate(data[i]))
ans = 0
for r_0 in range(len(data[0])+1):
    for r_1 in range(len(data[1])+1):
        for r_2 in range(len(data[2])+1):
            for r_3 in range(len(data[3])+1):
                if (r_0 * base) + (r_1 * (base + 1)) + (r_2 * (base + 2)) + (r_3 * (base + 3)) <= W:
                    cand = 0
                    if r_0 >= 1:
                        cand += data[0][r_0-1]
                    if r_1 >= 1:
                        cand += data[1][r_1-1]
                    if r_2 >= 1:
                        cand += data[2][r_2-1]
                    if r_3 >= 1:
                        cand += data[3][r_3-1]
                    ans = max(ans, cand)
print(ans)

Solution (Python):
N,W = map(int,input().split())
w1,v1 = map(int,input().split())
d = [[-v1],[],[],[]]
for i in range(N-1):
    w,v = map(int,input().split())
    x = w - w1
    d[x].append(-v)
d[0].sort()
n0 = len(d[0])
d[1].sort()
n1 = len(d[1])
d[2].sort()
n2 = len(d[2])
d[3].sort()
n3 = len(d[3])
s0 = [0]
s1 = [0]
s2 = [0]
s3 = [0]
for i in range(n0):
    x = s0[-1] + d[0][i]
    s0.append(x)
for i in range(n1):
    x = s1[-1] + d[1][i]
    s1.append(x)
for i in range(n2):
    x = s2[-1] + d[2][i]
    s2.append(x)
for i in range(n3):
    x = s3[-1] + d[3][i]
    s3.append(x)
d = [[[[0 for i in range(n3+1)] for j in range(n2+1)] for k in range(n1+1)] for l in range(n0+1)]
for i in range(n0+1):
    for j in range(n1+1):
        for k in range(n2+1):
            for l in range(n3+1):
                s = s0[i] + s1[j] + s2[k] + s3[l]
                s = -s
                x = w1*(i+j+k+l) + j + 2*k + 3*l
                if x <= W:
                    d[i][j][k][l] = s
ans = 0
for i in range(n0+1):
    for j in range(n1+1):
        for k in range(n2+1):
            for l in range(n3+1):
                x = d[i][j][k][l]
                ans = max(ans,x)
print(ans)

Solution (Python):
def makelst(lst, v):
    for i in range(N):
        if wv[i][0] == v:
            lst.append(wv[i][1])
    lst.sort(reverse=True)

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
v1cnt = W // wv[0][0]
v2cnt = W // (wv[0][0] + 1)
v3cnt = W // (wv[0][0] + 2)
v4cnt = W // (wv[0][0] + 3)
v1, v2, v3, v4 = [], [], [], []
makelst(v1, wv[0][0])
makelst(v2, wv[0][0] + 1)
makelst(v3, wv[0][0] + 2)
makelst(v4, wv[0][0] + 3)

[0] + v1, [0] + v2, [0] + v3, [0] + v4

ans = 0

v1cnt = min(v1cnt, len(v1))
v2cnt = min(v2cnt, len(v2))
v3cnt = min(v3cnt, len(v3))
v4cnt = min(v4cnt, len(v4))
ru1 = [0] * (v1cnt + 1)
ru2 = [0] * (v2cnt + 1)
ru3 = [0] * (v3cnt + 1)
ru4 = [0] * (v4cnt + 1)
for i in range(1, v1cnt + 1):
    ru1[i] = ru1[i - 1] + v1[i - 1]

for i in range(1, v2cnt + 1):
    ru2[i] = ru2[i - 1] + v2[i - 1]

for i in range(1, v3cnt + 1):
    ru3[i] = ru3[i - 1] + v3[i - 1]

for i in range(1, v4cnt + 1):
    ru4[i] = ru4[i - 1] + v4[i - 1]

for i in range(len(ru1)):
    for j in range(len(ru2)):
        for k in range(len(ru3)):
            for l in range(len(ru4)):
                wtmp = (i * wv[0][0]) + (j * (wv[0][0] + 1)) + (k * (wv[0][0] + 2)) + (l * (wv[0][0] + 3))
                if wtmp <= W:
                    ans = max(ans, ru1[i] + ru2[j] + ru3[k] + ru4[l])

print(ans)

Solution (Python):
def makelst(lst, v):
    for i in range(N):
        if wv[i][0] == v:
            lst.append(wv[i][1])
    lst.sort(reverse=True)

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
v1cnt = W // wv[0][0]
v2cnt = W // (wv[0][0] + 1)
v3cnt = W // (wv[0][0] + 2)
v4cnt = W // (wv[0][0] + 3)
v1, v2, v3, v4 = [], [], [], []
makelst(v1, wv[0][0])
makelst(v2, wv[0][0] + 1)
makelst(v3, wv[0][0] + 2)
makelst(v4, wv[0][0] + 3)

[0] + v1, [0] + v2, [0] + v3, [0] + v4

ans = 0

v1cnt = min(v1cnt, len(v1))
v2cnt = min(v2cnt, len(v2))
v3cnt = min(v3cnt, len(v3))
v4cnt = min(v4cnt, len(v4))
ru1 = [0] * (v1cnt + 1)
ru2 = [0] * (v2cnt + 1)
ru3 = [0] * (v3cnt + 1)
ru4 = [0] * (v4cnt + 1)
for i in range(1, v1cnt + 1):
    ru1[i] = ru1[i - 1] + v1[i - 1]

for i in range(1, v2cnt + 1):
    ru2[i] = ru2[i - 1] + v2[i - 1]

for i in range(1, v3cnt + 1):
    ru3[i] = ru3[i - 1] + v3[i - 1]

for i in range(1, v4cnt + 1):
    ru4[i] = ru4[i - 1] + v4[i - 1]

for i in range(len(ru1)):
    for j in range(len(ru2)):
        for k in range(len(ru3)):
            for l in range(len(ru4)):
                wtmp = (i * wv[0][0]) + (j * (wv[0][0] + 1)) + (k * (wv[0][0] + 2)) + (l * (wv[0][0] + 3))
                if wtmp <= W:
                    ans = max(ans, ru1[i] + ru2[j] + ru3[k] + ru4[l])

print(ans)

Solution (Python):
from itertools import product, accumulate
import sys
sys.stdin.readline

def main():
    N, W = map(int, input().split())
    V = [[] for _ in range(4)]
    w1 = 0
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0: w1 = w
        V[w-w1].append(v)
    U = []
    for i in range(4):
        U.append([0] + list(accumulate(sorted(V[i], reverse=True))))

    ans = 0
    for prod in product(*[range(len(U[i])) for i in range(4)]):
        if sum((i+w1)*p for i, p in enumerate(prod)) <= W:
            ans = max(ans, sum(U[i][p] for i, p in enumerate(prod)))
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
wv = [LIST() for _ in range(N)]
w0 = wv[0][0]

dic = defaultdict(list)
for w, v in wv:
	dic[w].append(v)

for key in dic:
	dic[key].sort(reverse=True)
	dic[key] = [0] + dic[key]
	dic[key] = list(accumulate(dic[key]))

for x in [w0, w0+1, w0+2, w0+3]:
	if not dic[x]:
		dic[x] = [0]


ans = 0
for a in range(len(dic[w0])):
	for b in range(len(dic[w0+1])):
		for c in range(len(dic[w0+2])):
			for d in range(len(dic[w0+3])):
				w = w0*a + (w0+1)*b + (w0+2)*c + (w0+3)*d
				s = dic[w0][a] + dic[w0+1][b] + dic[w0+2][c] + dic[w0+3][d]
				if w <= W:
					ans = s if ans < s else ans
print(ans)

Solution (Python):
n,W=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
w1=l[0][0]
l.sort(key=lambda x : x[1]*-1)
l0,l1,l2,l3 = [],[],[],[]
for w,v in l:
    if w==w1:
        l0.append(v)
    if w==w1+1:
        l1.append(v)
    if w==w1+2:
        l2.append(v)
    if w==w1+3:
        l3.append(v)
sl1,sl2,sl3,sl0=[0],[0],[0],[0]
tl=0
for i in range(len(l0)):
    tl += l0[i]
    sl0.append(tl)
tl=0
for i in range(len(l1)):
    tl += l1[i]
    sl1.append(tl)
tl=0
for i in range(len(l2)):
    tl += l2[i]
    sl2.append(tl)
tl=0
for i in range(len(l3)):
    tl += l3[i]
    sl3.append(tl)
res = 0
for a in range(len(sl0)):
    for b in range(len(sl1)):
        for c in range(len(sl2)):
            for d in range(len(sl3)):
                if w1*a+(w1+1)*b+(w1+2)*c+(w1+3)*d <= W:
                    res = max(res,sl0[a]+sl1[b]+sl2[c]+sl3[d])
print(res)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, lim = MI()
    ww = []
    vv = []
    for _ in range(n):
        w, v = MI()
        ww.append(w)
        vv.append(v)
    w0=ww[0]
    
    dp=[[0]*(3*n+1) for _ in range(n+1)]
    for w,v in zip(ww,vv):
        for i in range(n,0,-1):
            sj=min(lim-i*w0,3*n)
            for j in range(sj,-1,-1):
                nj=j-(w-w0)
                if nj<0:break
                dp[i][j]=max(dp[i][j],dp[i-1][nj]+v)
    
    print(max(max(row) for row in dp))

main()

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])
    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):
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):
    d=w-i*(w0+3)
    if d>=0:
        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
    else:
        break


print(ma)