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):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys
n,W = ma()
wm=3*(n-1)
dp=[[[0]*(wm+1) for j in range(n+1)] for j in range(n+1) ] 
wv=[]
for i in range(n):
    w,v=ma()
    if i==0:
        wv.append((0,v))
        w0=w
    else:
        wv.append((w-w0,v))

for i in range(n):
    w,v = wv[i]
    for j in range(1,i+2):
        
        for ww in range(wm+1):
            dp[i][j][ww]=dp[i-1][j][ww]
            if ww-w>=0:
                dp[i][j][ww]=max(dp[i-1][j-1][ww-w]+v,dp[i][j][ww])
ans=0
for j in range(n+1):
    for w in range(wm+1):
        if j*w0 + w<=W:
            ans=max(ans,dp[n-1][j][w])
print(ans)

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    w0 = weight[0]
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w0].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            return v
        ans = 0
        w_next = w
        for j in range(len(csums[i])):
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))
            w_next += w0 + i

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            w_next = w + (w_min + i) * j
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            w_next = w + (w_min + i) * j
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            ans = max(ans, rec(i + 1, w + (w_min + i) * j, v + csums[i][j]))

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, vec):
        if i == 4:
            ans = 0
            w_total = 0
            for j in range(4):
                w_total += (w_min + j) * vec[j]
            if w_total > W:
                return -1
            for j in range(4):
                ans += csums[j][vec[j]]
            return ans
        ans = 0
        for j in range(len(csums[i])):
            vec.append(j)
            ans = max(ans, rec(i + 1, vec))
            vec.pop()
        return ans

    print(rec(0, []))
    return


if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Bag = dd(lambda:0)
Bag[0] = 0
for w,v in Items:
    temp = [(key+w,Bag[key]+v) for key in Bag if key + w <= W]
    for key,value in temp:
        Bag[key] = max(Bag[key],value)
ans = max(Bag.values())
print(ans)

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

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

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

result = 0
for i in range(len(vs[0])):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1])):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2])):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = vs[0][i] + vs[1][j] + vs[2][k]
            for l in range(len(vs[3])):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                result = max(result, t + vs[3][l])
print(result)

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

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

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0]) + 1):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1]) + 1):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2]) + 1):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = 0
            if i != 0:
              t += vs[0][i - 1]
            if j != 0:
              t += vs[1][j - 1]
            if k != 0:
              t += vs[2][k - 1]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                if l == 0:
                    result = max(result, t)
                else:
                    result = max(result, t + vs[3][l -1])
print(result)

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

dp = [[[-10**10]*(320) for j in range(100)] for i in range(N)]


dp[0][0][0] = 0
dp[0][1][0] = wv[0][1]
for i in range(1,N):
    for j in range(100):
        for k in range(320):
            dp[i][j][k]=dp[i-1][j][k]
            if j-1>=0 and k+wv[0][0]-wv[i][0]>=0:
                dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k+wv[0][0]-wv[i][0]]+wv[i][1])
    
ans = 0
for j in range(100):
    for k in range(320):
        if j*wv[0][0]+k <= W:
            ans = max(ans,dp[N-1][j][k])


print(ans)

Solution (Python):
N, W = map(int, input().split())
w0 = 0
Items = []
for _ in range(N):
    w, v = map(int, input().split())
    if _ == 0:
        w0 = w
        w = 0
    else:
        w -= w0
    Items.append((w, v))

DP = [[[0] * (N * 4) for _ in range(N * 4)] for __ in range(N+1)]

for i, (w, v) in enumerate(Items, 1):
    for j in range(1, N * 4):
        if i < j:
            break
        for k in range(N * 4):
            if k < w:
                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] + v)

ans = 0
for j, value in enumerate(DP[N]):
    for k, v in enumerate(value):
        if j * w0 + k <= W:
            ans = max(ans, v)
print(ans)

Solution (Python):
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Bag = dd(lambda:0)
Bag[0] = 0
for w,v in Items:
    temp = [(key+w,Bag[key]+v) for key in Bag if key + w <= W]
    for key,value in temp:
        Bag[key] = max(Bag[key],value)
ans = max(Bag.values())
print(ans)

Solution (Python):
from collections import Counter, defaultdict
N, W = map(int, input().split())
wv_dict = defaultdict(list)
for i in range(N):
    w, v = map(int, input().split())
    wv_dict[w] += [v]
sorted_w = sorted(wv_dict.keys())
w0 = sorted_w[0]
w_list = [w0 + i for i in range(4)]
for key in w_list:
    sorted_v = sorted(wv_dict[key], reverse=True)
    for i in range(len(sorted_v)-1):
        sorted_v[i+1] += sorted_v[i]
    wv_dict[key] = [0] + sorted_v
w0, w1, w2, w3 = [w0 + i for i in range(4)]
ans = 0
for c0 in range(len(wv_dict[w0])):
    for c1 in range(len(wv_dict[w0+1])):
        for c2 in range(len(wv_dict[w0+2])):
            for c3 in range(len(wv_dict[w0+3])):
                if w0 * c0 + w1 * c1 + \
                    w2 * c2 + w3 * c3 <= W:
                    v = wv_dict[w0][c0] + wv_dict[w1][c1] + \
                        wv_dict[w2][c2] + wv_dict[w3][c3]
                    ans = max(ans, v)

print(ans)

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

n, weight = map(int, input().split())
w, v = [0]*n, [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())

base = w[0]

for i in range(n):
    w[i] -= base


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

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

ans = 0
for i in range(n+1):
    for j in range(3*n+1):
        if base * i + j <= weight and ans < dp[i][j]:
            ans = dp[i][j]

print(ans)

Solution (Python):


N, W = map(int, input().split())
INF = 10**13
DP = [[[-INF for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
w0, v = map(int, input().split())
DP[1][0][0] = 0
DP[1][1][0] = v

for i in range(2,N+1):
  w, v = map(int, input().split())
  w -= w0
  for j in range(N+1):
    for k in range(3*N+1):
      if k-w >= 0:
        DP[i][j][k] = max(DP[i-1][j-1][k-w] + v, DP[i-1][j][k])
      else:
        DP[i][j][k] = DP[i-1][j][k]





ans = max([max([DP[N][j][k] for k in range(min(3*N,W-w0*j)+1)]) if W-w0*j >= 0 else -INF for j in range(N+1)])
print(ans)

Solution (Python):
n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
num = wv[0][0]
dp = [[-float("inf") for i in range(3 * (n - 1) + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    w, v = wv[i][0], wv[i][1]
    w -= num
    for j in range(n - 1, -1, -1):
        for k in range(3 * (n - 1) + 1 - w):
            dp[j + 1][k + w] = max(dp[j + 1][k + w], dp[j][k] + v)
ans = 0
for i in range(3 * (n - 1) + 1):
    for j in range(n + 1):
        if j * num + i <= W:
            ans = max(ans, dp[j][i])
print(ans)

Solution (Python):
n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
num = wv[0][0]
dp = [[-float("inf") for i in range(3 * (n - 1) + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    w, v = wv[i][0], wv[i][1]
    w -= num
    for j in range(n - 1, -1, -1):
        for k in range(3 * (n - 1) + 1 - w):
            dp[j + 1][k + w] = max(dp[j + 1][k + w], dp[j][k] + v)
ans = 0
for i in range(3 * (n - 1) + 1):
    for j in range(n + 1):
        if j * num + i <= W:
            ans = max(ans, dp[j][i])
print(ans)

Solution (Python):
from collections import *
N,W = map(int,input().split())
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w1,v1 = map(int,input().split())
  for w2,v2 in dp.copy().items():
    if w1+w2<=W:
      dp[w1+w2] = max(dp[w1+w2],v1+v2)

print(max(dp.values()))

Solution (Python):
from collections import *
N,W = map(int,input().split())
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w,v = map(int,input().split())
  for k,b in dp.copy().items():
    if k+w<=W:
      dp[k+w] = max(dp[k+w],b+v)

print(max(dp.values()))

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

n, wei = map(int,readline().split())

w,v = [],[]
for i in range(n):
    wi, vi = map(int,readline().split())
    w.append(wi)
    v.append(vi)

w1,w2,w3,w4 = [],[],[],[]
for i in range(n):
    if w[i] == w[0]: w1.append(v[i])
    if w[i] == w[0] + 1: w2.append(v[i])
    if w[i] == w[0] + 2: w3.append(v[i])
    if w[i] == w[0] + 3: w4.append(v[i])

w1 = [0] + list(accumulate(sorted(w1, reverse=True)))
w2 = [0] + list(accumulate(sorted(w2, reverse=True)))
w3 = [0] + list(accumulate(sorted(w3, reverse=True)))
w4 = [0] + list(accumulate(sorted(w4, reverse=True)))

ans = 0
for i in range(len(w1)):
    for j in range(len(w2)):
        for k in range(len(w3)):
            for l in range(len(w4)):
                vsum = w1[i] + w2[j] + w3[k] + w4[l];
                wsum = w[0]*i + (w[0]+1)*j + (w[0]+2)*k + (w[0]+3)*l;
                if wsum <= wei: ans = max(ans,vsum)

print(ans)

Solution (Python):

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

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

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

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

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

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

Solution (Python):
N , W = map(int,input().split())
mono = [tuple(map(int,input().split())) for i in range(N)]
w1 = mono[0][0]
dp = [[-1 for i in range(301)] for j in range(N+1)]
dp[0][0] = 0 

for i in range(N):
    p = mono[i][0] - w1
    for j in reversed(range(N)):
        for k in reversed(range(301)):
            if dp[j][k] != -1:
                dp[j+1][k+p] = max(dp[j+1][k+p],dp[j][k]+mono[i][1])

ans = 0
for i in range(N+1):
    for j in range(301):
        if i*w1 + j <= W:
            ans = max(ans,dp[i][j])

print(ans)

Solution (Python):




















n, w_limit = list(map(int, input().split()))

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

weight_base = baggage[0][0]





for i in range(n):
    baggage[i][0] -= weight_base

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

for l in range(baggage[0][0], 3*n):
    dp[0][1][l] = baggage[0][1]

for i in range(1, n):
    for k in range(1, n+1):
        for l in range(3*n+1):
            if l - baggage[i][0] >= 0:
                dp[i][k][l] = max(dp[i-1][k][l], dp[i-1][k-1][l - baggage[i][0]] + baggage[i][1])
            else:
                dp[i][k][l] = dp[i-1][k][l]

valid_min_num = w_limit // (weight_base+3)
valid_max_num = w_limit // weight_base

ans = 0
for num in range(valid_min_num, min(valid_max_num, n) + 1):
    weight_rest = w_limit - weight_base * num
    if weight_rest >= 3*n:
        weight_rest = 3*n

    
    ans = max(ans, dp[n-1][num][weight_rest])

print(ans)

Solution (Python):




















n, w_limit = list(map(int, input().split()))

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

weight_base = baggage[0][0]





for i in range(n):
    baggage[i][0] -= weight_base

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

for l in range(baggage[0][0], 3*n):
    dp[0][1][l] = baggage[0][1]

for i in range(1, n):
    for k in range(1, n+1):
        for l in range(3*n+1):
            if l - baggage[i][0] >= 0:
                dp[i][k][l] = max(dp[i-1][k][l], dp[i-1][k-1][l - baggage[i][0]] + baggage[i][1])
            else:
                dp[i][k][l] = dp[i-1][k][l]

valid_min_num = w_limit // (weight_base+3)
valid_max_num = w_limit // weight_base

ans = 0
for num in range(valid_min_num, min(valid_max_num, n) + 1):
    weight_rest = w_limit - weight_base * num
    if not 0 <= weight_rest:  
        continue
    elif weight_rest >= 3*n:
        weight_rest = 3*n

    
    ans = max(ans, dp[n-1][num][weight_rest])

print(ans)

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    """
    ナップサックで重さを飛び飛びにしてdpを軽くしなくても、
    そもそも重さが４パターンだから全探索で解けたのか。。。。。。
    """
    N, W = map(int, input().split())
    item = [[] for _ in range(4)]
    length = [1, 0, 0, 0]
    w0, v0 = map(int, input().split())
    item[0].append(v0)
    for _ in range(N - 1):
        w, v = map(int, input().split())
        item[w - w0].append(v)
        length[w - w0] += 1
    for i in range(4): item[i].sort(reverse=True)

    
    S = []
    for i in range(4):
        S.append([0] + list(accumulate(item[i])))

    ans = 0
    for a in range(length[0] + 1):
        for b in range(length[1] + 1):
            for c in range(length[2] + 1):
                for d in range(length[3] + 1):
                    weight = a * w0 + b * (w0 + 1) + c * (w0 + 2) + d * (w0 + 3)
                    if weight > W: continue
                    ans = max(ans, S[0][a] + S[1][b] + S[2][c] + S[3][d])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    N, W = map(int, input().split())
    w0, v0 = map(int, input().split())
    item = [0, w0 * offset + v0]
    weight_sum, value_sum = w0, v0
    for _ in range(1, N):
        w, v = map(int, input().split())
        item.append(w * offset + v)
        weight_sum += w
        value_sum += v

    if W < w0:
        print(0)
        return
    if weight_sum <= W:
        print(value_sum)
        return

    if w0 <= 3 * (N - 1):
        
        dp = [[0] * (W + 1) for _ in range(N + 1)]
        for i in range(1, N + 1):
            w, v = item[i] // offset, item[i] % offset
            for j in range(w): dp[i][j] = dp[i - 1][j]
            for j in range(w, W + 1):
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        print(dp[N][W])
        return

    
    dp = [[[0] * (3 * (N - 1) + 1) for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = item[i] // offset, item[i] % offset
        for j in range(i + 1):
            for k in range(3 * (N - 1) + 1):
                weight = j * w0 + k
                q, r = (weight - w) // w0, (weight - w) % w0
                if weight < w:
                    dp[i][j][k] = dp[i - 1][j][k]
                elif (weight - w) % w0 > 3 * (N - 1):
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][q][3 * (N - 1)] + v)
                else:
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][q][r] + v)
    q, r = W // w0, min(W % w0, 3 * (N - 1))
    print(dp[N][q][r])


if __name__ == "__main__":
    main()

Solution (Python):
n,w=map(int,input().split())
x1,y1=map(int,input().split())
d={x1:[y1],x1+1:[],x1+2:[],x1+3:[]}
for _ in range(n-1):
    x,y=map(int,input().split())
    d[x].append(y)
d={k:[0]+sorted(d[k],reverse=True) for k in d}
vm=0
v1,w1=0,0
for e in d[x1]:
    v1+=e
    w1+=0 if e==0 else x1
    v2,w2=0,0
    for f in d[x1+1]:
        v2+=f
        w2+=0 if f==0 else x1+1
        v3,w3=0,0
        for g in d[x1+2]:
            v3+=g
            w3+=0 if g==0 else x1+2
            v4,w4=0,0
            for h in d[x1+3]:
                v4+=h
                w4+=0 if h==0 else x1+3
                ws=w1+w2+w3+w4
                vs=v1+v2+v3+v4
                if ws<=w:
                    vm=max(vm,vs)
print(vm)

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

dp={0:0}

for cw,cv in gds:
    tmp={}

    for key,value in dp.items():
        if key in tmp:
            tmp[key]=max(tmp[key],value)
        else:
            tmp[key]=value
        
        if cw+key<=w:
            if cw+key in tmp:
                tmp[cw+key]=max(tmp[cw+key],value+cv)
            else:
                tmp[cw+key]=value+cv
    
    dp=tmp

print(max(dp.values()))

Solution (Python):
N,W = map(int,input().split())
wv = []
base_w = float('inf')
for _ in range(N):
    w, v = (int(x) for x in input().split())
    wv.append([w, v])
    base_w = min(base_w, w)

dp = [[-10000000000 for i in range(100*3+1)] for j in range(N+1)]

dp[0][0] = 0


for ws ,vs in wv:
    ws -= base_w
    for h in range(N+1, 0, -1):
        for w in range(100*3, -1, -1):
            if 0 <= w-ws:
                if dp[h-1][w-ws] != -10000000000:
                    dp[h][w] = max(dp[h][w], dp[h-1][w-ws]+vs)

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

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

V = [[], [], [], []]
for wi, vi in zip(w, v):
  V[wi - w[0]].append(vi)

for vv in V:
  vv.sort(reverse=True)

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

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):
n,w = map(int,input().split())
import collections
dic = collections.defaultdict(list)
w_min = float('inf')
for _ in range(n):
    a,b = map(int,input().split())
    dic[a].append(b)
    dic[a].sort(reverse = True)
    w_min = min(w_min,a)

sum_dic = collections.defaultdict(list)
for key,li in dic.items():
    if len(sum_dic[key])==0:
        sum_dic[key].append(0)
    for l in li:
        sum_dic[key].append(sum_dic[key][-1] + l)
ans = 0

for i in range(4):
    if len(sum_dic[w_min+i])==0:
        sum_dic[w_min+i].append(0)

for i,v1 in enumerate(sum_dic[w_min]):
        for j,v2 in enumerate(sum_dic[w_min+1]):
            for k,v3 in enumerate(sum_dic[w_min+2]):
                for l,v4 in enumerate(sum_dic[w_min+3]):
                    if (i+j+k+l)*w_min + j+2*k+3*l<=w:
                        ans = max(ans,v1+v2+v3+v4)
print(ans)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,W = MI()
w1,v = MI()
v0,v1,v2,v3 = [v],[],[],[]  
for i in range(N-1):
    w,v = MI()
    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)
N0,N1,N2,N3 = len(v0),len(v1),len(v2),len(v3)

from itertools import accumulate
v0_accumulate = [0] + list(accumulate(v0))
v1_accumulate = [0] + list(accumulate(v1))
v2_accumulate = [0] + list(accumulate(v2))
v3_accumulate = [0] + list(accumulate(v3))

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):  
                if w1*i + (w1+1)*j + (w1+2)*k + (w1+3)*l <= W:
                    ans = max(ans,v0_accumulate[i]+v1_accumulate[j]+v2_accumulate[k]+v3_accumulate[l])
print(ans)

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *wv = map(int, read().split())

    w0 = wv[0]
    weight = [[] for _ in range(4)]
    for w, v in zip(*[iter(wv)] * 2):
        weight[w - w0].append(v)

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

    csum = [[0] for _ in range(4)]
    for i in range(4):
        csum[i].extend(accumulate(weight[i]))

    def dfs(w, v, idx):
        if idx == 4:
            return v

        ans = 0
        for i in range(len(csum[idx])):
            if w + (w0 + idx) * i > W:
                break
            ans = max(ans, dfs(w + (w0 + idx) * i, v + csum[idx][i], idx + 1))

        return ans

    print(dfs(0, 0, 0))

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve1(N, W, weight, value):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if w - weight[i] >= 0:
                dp[i + 1][w] = dp[i][w - weight[i]] + value[i]
            if dp[i + 1][w] < dp[i][w]:
                dp[i + 1][w] = dp[i][w]

    return dp[N][W]


def solve2(N, W, weight, value):
    w0 = weight[0]
    M = W // w0
    if M == 0:
        return 0

    weight_adj = [w - w0 for w in weight]
    w_total = sum(weight_adj)

    dp = [[[0] * (w_total + 1) for j in range(N + 1)] for i in range(M + 1)]
    for i in range(M):
        for j in range(N):
            for w in range(w_total + 1):
                if w - weight_adj[j] >= 0:
                    dp[i + 1][j + 1][w] = dp[i][j][w - weight_adj[j]] + value[j]
                if dp[i + 1][j + 1][w] < dp[i + 1][j][w]:
                    dp[i + 1][j + 1][w] = dp[i + 1][j][w]
                if dp[i + 1][j + 1][w] < dp[i][j + 1][w]:
                    dp[i + 1][j + 1][w] = dp[i][j + 1][w]

    return max(dp[M][N][min(W - w0 * M, w_total)], dp[M - 1][N][min(W - w0 * (M - 1), w_total)])


def main():
    N, W, *wv = map(int, read().split())
    weight = wv[::2]
    value = wv[1::2]

    if weight[0] < 500:
        ans = solve1(N, W, weight, value)
    else:
        ans = solve2(N, W, weight, value)

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import numpy as np

def main():
    def itrsum(arr):
        n=len(arr)
        tri=np.array([[i>=j for i in range(n)] for j in range(n+1)])
        return np.dot(tri,arr).astype('int64')
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    
    arr=[[x for x in t if x[0]==w1+i] for i in range(4)]
    arr=[l for l in arr]
    lenarr=list(map(len,arr))
    arr0=[itrsum(np.array(sorted([x[0] for x in l]),dtype='int64')) for l in arr]
    arr1=[itrsum(np.array(sorted([x[1] for x in l]),dtype='int64')) for l in arr]
    
    arr=np.array(arr)
    arrw=0
    arrv=0
    for i in range(4):
        arrw=np.ravel(arr0[i].reshape(lenarr[i]+1,1)+np.array([arrw]))
        arrv=np.ravel(arr1[i].reshape(lenarr[i]+1,1)+np.array([arrv]))
    
    
    
    
    
    
    ansarr=arrv[arrw<=w]
    print(np.max(ansarr))
    
    

if __name__=='__main__':
    main()

Solution (Python):
from collections import defaultdict
N,W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
DP = defaultdict(int)
DP[0] = 0
for weight, value in wv:
  exists = list(DP.items())
  for key, total in exists:
    new_key = key + weight
    if new_key > W:
      continue
    new_total = total + value
    if DP[new_key] < new_total:
      DP[new_key] = new_total

print(max(DP.values()))

Solution (Python):
N,W = map(int,input().rstrip().split(" "))
DP = [[-1 for _ in range(310)] for _ in range(N+1)]
DP[0][0] = 0
ans = 0
for i in range(N):
    w,v = map(int,input().rstrip().split(" "))
    if i == 0: w1 = w
    for i2 in range(i,-1,-1):
        for i3 in range(309,-1,-1):
            if DP[i2][i3] != -1:
                DP[i2 + 1][i3 + (w - w1)] = max(DP[i2 + 1][i3 + (w - w1)],DP[i2][i3]+v)
                if i2 * w1 + i3 + w <= W:
                    ans = max(DP[i2 + 1][i3 + (w - w1)],ans)
print(ans)