Problem:
 Score : 400 points    Problem Statement You have N items and a bag of strength W .
The i -th item has a weight of w_i and a value of v_i .  You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W .  Your objective is to maximize the total value of the selected items.      Constraints  1 ≤ N ≤ 100  1 ≤ W ≤ 10^9  1 ≤ w_i ≤ 10^9  For each i = 2,3,...,N , w_1 ≤ w_i ≤ w_1 + 3 .  1 ≤ v_i ≤ 10^7  W , each w_i and v_i are integers.         Input Input is given from Standard Input in the following format:  N  W  w_1  v_1  w_2  v_2 : w_N  v_N       Output Print the maximum possible total value of the selected items.        Sample Input 1 4 6
2 1
3 4
4 10
3 4      Sample Output 1 11  The first and third items should be selected.       Sample Input 2 4 6
2 1
3 7
4 10
3 6      Sample Output 2 13  The second and fourth items should be selected.       Sample Input 3 4 10
1 100
1 100
1 100
1 100      Sample Output 3 400  You can take everything.       Sample Input 4 4 1
10 100
10 100
10 100
10 100      Sample Output 4 0  You can take nothing.

Solution (Python):
n,w = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    if i == 0:
      ti = x1
      zero = 0
      iti = 0
      ni = 0
      san = 0
    if x1 == ti:
      zero += 1
    elif x1 == ti+1:
      iti += 1
    elif x1 == ti+2:
      ni += 1
    else:
      san +=1
    x.append([x1,y1])
x.sort()
zer = x[:zero]
one = x[zero:iti+zero]
two = x[iti+zero:iti+ni+zero]
three = x[iti+ni+zero:zero+iti+ni+san]
zer.append([0,0])
one.append([0,0])
two.append([0,0])
three.append([0,0])
zer = sorted(zer,key = lambda x: -x[1])
one = sorted(one,key = lambda x: -x[1])
two = sorted(two,key = lambda x: -x[1])
three = sorted(three,key = lambda x: -x[1])
ans = 0
zer0 = [0]* len(zer)+ [0]
one0 = [0]* len(one)+ [0]
two0 = [0]* len(two)+ [0]
three0 = [0]* len(three)+ [0]
zerk = [0]* len(zer)+ [0]
onek = [0]* len(one)+ [0]
twok = [0]* len(two)+ [0]
threek = [0]* len(three)+ [0]
for i in range(1,len(zer)+1):
  zer0[i] = zer0[i-1] + zer[i-1][0]
  zerk[i] = zerk[i-1] + zer[i-1][1]
for i in range(1,len(one)+1):
  one0[i] = one0[i-1] + one[i-1][0]
  onek[i] = onek[i-1] + one[i-1][1]
for i in range(1,len(two)+1):
  two0[i] = two0[i-1] + two[i-1][0]
  twok[i] = twok[i-1] + two[i-1][1]
for i in range(1,len(three)+1):
  three0[i] = three0[i-1] + three[i-1][0]
  threek[i] = threek[i-1] + three[i-1][1]
for i in range(len(zer)):
  for j in range(len(one)):
    for k in range(len(two)):
      for l in range(len(three)):
        omo = zer0[i] + one0[j] + two0[k] + three0[l]
        kati  = zerk[i] + onek[j] + twok[k] + threek[l]
        if omo <= w:
          ans = max(ans,kati)
print(ans)

Solution (Python):
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[] for i in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
ans=0
s=[[0 for j in range(len(t[i])+1)] for i in range(4)]
for i in range(4):
    for j in range(1,len(t[i])+1):
        s[i][j]=s[i][j-1]+t[i][j-1]
for a0 in range(len(s[0])):
    for a1 in range(len(s[1])):
        for a2 in range(len(s[2])):
            for a3 in range(len(s[3])):
                tmp=s[0][a0]+s[1][a1]+s[2][a2]+s[3][a3]
                wt=a0*w[0]+a1*(w[0]+1)+a2*(w[0]+2)+a3*(w[0]+3)
                if wt>W:
                    continue
                if ans<tmp:
                    ans=tmp
print(ans)

Solution (Python):
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[] for i in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
ans=0
s=[[0 for j in range(len(t[i])+1)] for i in range(4)]
for i in range(4):
    for j in range(1,len(t[i])+1):
        s[i][j]=s[i][j-1]+t[i][j-1]
for a0 in range(len(s[0])):
    for a1 in range(len(s[1])):
        for a2 in range(len(s[2])):
            for a3 in range(len(s[3])):
                tmp=s[0][a0]+s[1][a1]+s[2][a2]+s[3][a3]
                wt=a0*w[0]+a1*(w[0]+1)+a2*(w[0]+2)+a3*(w[0]+3)
                if wt>W:
                    continue
                if ans<tmp:
                    ans=tmp
print(ans)

Solution (Python):
n, m = map(int,raw_input().split())

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

w,v = map(int,raw_input().split())
arr[0].append(v)
arr[1].append(0)
arr[2].append(0)
arr[3].append(0)

for i in range(1,n):
	weight , value = map(int,raw_input().split())

	arr[weight - w].append(value)

ans = 0

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


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

print ans

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and l < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k, l+1) + items[ws[3]][l])

        return ret

    return f(W, 0, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and l < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k, l+1) + items[ws[3]][l])

        return ret

    return f(W, 0, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

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

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w], v_cur+v)


print(max(dp.values()))

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

w0 = wv[0][0]
wv_dict = {w0:[], w0+1:[], w0+2:[], w0+3:[]}
for w, v in wv:
    wv_dict[w].append(v)
for w, vs in wv_dict.items():
    vs = sorted(vs)[::-1]
    wv_dict[w] = [0]
    for v in vs:
        wv_dict[w].append(v + wv_dict[w][-1])


ans = 0
for i in range(len(wv_dict[w0])):
    for j in range(len(wv_dict[w0+1])):
        for k in range(len(wv_dict[w0+2])):
            for l in range(len(wv_dict[w0+3])):
                w_sum = i*w0 + j*(w0+1) + k*(w0+2) + l*(w0+3)
                if w_sum > W: continue

                ans = max(ans, wv_dict[w0][i]+wv_dict[w0+1][j]+wv_dict[w0+2][k]+wv_dict[w0+3][l])
print(ans)

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

w_std,v = map(int,input().split())
v_list[0].append(v)
for i in range(N-1):
    wi,vi = map(int,input().split())
    v_list[wi-w_std].append(vi)
for i in range(4):
    v_list[i].sort(reverse=True)
    v_list[i].insert(0,0)

for i in range(4):
    if (len(v_list[i]) > 1):
        for j in range(1,len(v_list[i])):
            v_list[i][j] += v_list[i][j-1]

max_v = 0
for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len((v_list[2]))):
            for l in range(len(v_list[3])):
                if (W >= i*w_std+j*(w_std+1)+k*(w_std+2)+l*(w_std+3)):
                    max_v = max(max_v,v_list[0][i]+v_list[1][j]+v_list[2][k]+v_list[3][l])
print(max_v)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


w,v = map(int,(input().split()))
min_w = w
wv[0].append(v)

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

wv[0].sort(reverse=True)
wv[1].sort(reverse=True)
wv[2].sort(reverse=True)
wv[3].sort(reverse=True)
L1 = len(wv[0])
L2 = len(wv[1])
L3 = len(wv[2])
L4 = len(wv[3])

SUM = 0
sum_wv1 = [0]
for i in range(L1):
	SUM += wv[0][i]
	sum_wv1.append(SUM)

SUM = 0
sum_wv2 = [0]
for i in range(L2):
	SUM += wv[1][i]
	sum_wv2.append(SUM)

SUM = 0
sum_wv3 = [0]
for i in range(L3):
	SUM += wv[2][i]
	sum_wv3.append(SUM)

SUM = 0
sum_wv4 = [0]
for i in range(L4):
	SUM += wv[3][i]
	sum_wv4.append(SUM)

ans = 0

for n1 in range(L1+1):
	for n2 in range(L2+1):
		for n3 in range(L3+1):
			for n4 in range(L4+1):
				weight = min_w*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
				if weight <= W:
					ans = max(ans,sum_wv1[n1]+sum_wv2[n2]+sum_wv3[n3]+sum_wv4[n4])

print(ans)

Solution (Python):
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    
    dp = defaultdict(int)
    dp[0] = 0  
    for w, v in Baggage:
        
        
        
        latest_dp = list(dp.items())
        for kw, kv in latest_dp:
            if kw + w <= W:
                dp[kw + w] = max(dp[kw + w], kv + v)
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print(d_simple_knapsack(N, W, Baggage))

Solution (Python):
from collections import defaultdict


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

dp[0] = 0

for w,v in WV:
    for new_w, new_v in list(dp.items()):
        if w + new_w <= W:
            dp[w + new_w] = max(dp[w + new_w], v + new_v)
            
print(max(dp.values()))

Solution (Python):
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    
    dp = defaultdict(int)
    dp[0] = 0  
    for w, v in Baggage:
        
        
        
        tmp = defaultdict(int)  
        for kw, kv in dp.items():
            if kw + w <= W:
                if kw + w in dp:
                    tmp[kw + w] = max(dp[kw + w], kv + v)
                else:
                    tmp[kw + w] = kv + v
        for key, value in tmp.items():
            dp[key] = value
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print(d_simple_knapsack(N, W, Baggage))

Solution (Python):

from collections import defaultdict

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

dp = defaultdict(int)

dp[0] = 0

for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

Solution (Python):
n,m=input().split()
N = int(n)
M = int(m)
w_list = []
v_list = []
w1_values = []
w2_values = []
w3_values = []
w4_values = []
sum_w1_values = []
sum_w2_values = []
sum_w3_values = []
sum_w4_values = []
sum_v1 = 0
sum_v2 = 0
sum_v3 = 0
sum_v4 = 0

for i in range(N):
	w,v = input().split()
	w = int(w)
	v = int(v)
	w_list.append(w)
	v_list.append(v)

w1 = w_list[0]
for j in range(N):
	if(w_list[j] == w1):
		w1_values.append(v_list[j])

	elif(w_list[j] == w1+1):
		w2_values.append(v_list[j])

	elif(w_list[j] == w1+2):
		w3_values.append(v_list[j])

	elif(w_list[j] == w1+3):
		w4_values.append(v_list[j])

w1_values.sort()
w1_values.reverse()
w2_values.sort()
w2_values.reverse()
w3_values.sort()
w3_values.reverse()
w4_values.sort()
w4_values.reverse()

for p in range(len(w1_values)):
	sum_v1 += w1_values[p]
	sum_w1_values.append(sum_v1)

for q in range(len(w2_values)):
	sum_v2 += w2_values[q]
	sum_w2_values.append(sum_v2)

for r in range(len(w3_values)):
	sum_v3 += w3_values[r]
	sum_w3_values.append(sum_v3)

for s in range(len(w4_values)):
	sum_v4 += w4_values[s]
	sum_w4_values.append(sum_v4)


sum_w1_values.insert(0,0)
sum_w2_values.insert(0,0)
sum_w3_values.insert(0,0)
sum_w4_values.insert(0,0)

max_value = 0
count = 0
for w in range(len(sum_w4_values)):
	for x in range(len(sum_w3_values)):
		for y in range(len(sum_w2_values)):
			for z in range(len(sum_w1_values)):
				count = w+x+y+z
				weight = (w1)*z + (w1+1)*y +(w1+2)*x + (w1+3)*w
				if(count<=N and weight<=M and max_value<(sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w])):
					max_value = sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w]


print(max_value)

Solution (Python):
n,w = map(int,input().split())
weighta = []
weightb = []
weightc = []
weightd = []
for i in range(n):
	wtemp,vtemp = map(int,input().split())
	if i == 0:
		weighta.append(vtemp)
		first = wtemp
	elif wtemp == first:
		weighta.append(vtemp)
	elif wtemp == first+1:
		weightb.append(vtemp)
	elif wtemp == first+2:
		weightc.append(vtemp)
	elif wtemp == first+3:
		weightd.append(vtemp)

weighta.sort()
weighta.reverse()
weightb.sort()
weightb.reverse()
weightc.sort()
weightc.reverse()
weightd.sort()
weightd.reverse()

cuma = [0]
for i in range(len(weighta)):
	cuma.append(weighta[i]+cuma[i])
cumb = [0]
for i in range(len(weightb)):
	cumb.append(weightb[i]+cumb[i])
cumc = [0]
for i in range(len(weightc)):
	cumc.append(weightc[i]+cumc[i])
cumd = [0]
for i in range(len(weightd)):
	cumd.append(weightd[i]+cumd[i])

wa = first
wb = first+1
wc = first+2
wd = first+3

max = 0
for a in range(len(weighta)+1):
	for b in range(len(weightb)+1):
		for c in range(len(weightc)+1):
			for d in range(len(weightd)+1):
				if wa*a + wb*b + wc*c + wd*d <= w:
					t = cuma[a]-cuma[0] + cumb[b]-cumb[0] + cumc[c]-cumc[0] + cumd[d]-cumd[0]
					if t > max:
						max = t
print(max)

Solution (Python):
from collections import defaultdict
N, W = map(int, input().split())
dd = defaultdict(int)
dd[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    ddOld = dd.copy()
    ddOld2 = dd.copy()
    for dk, dv in ddOld.items():
        dd[dk+w] = max(ddOld2[dk+w], dv+v)
ans = 0
for dk, dv in dd.items():
    if dk <= W:
        ans = max(ans, dv)
print(ans)

Solution (Python):
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(tuple(map(int, input().split())))
w0, v0 = wv[0]
L = (N+1) * 3
dp = [[-1] * L for _ in range(N + 1)]
dp[0][0] = 0
for w,v in wv :
    for k in range(N-1, -1,  -1):
        for t in range(len(dp[k])):
            if dp[k][t] >= 0:
                dp[k+1][t+w-w0] = max(dp[k][t] + v, dp[k+1][t + w - w0])
ans = 0
for k in range(N+1):
    if w0 * k  > W : continue
    ans = max(max(dp[k][:max(min(L, W - w0 * k + 1), 0)]), ans)
print(ans)

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

w, v = map(int,input().split())
w0 = w
V[0].append(v)

for _ in range(N-1):
    w, v = map(int,input().split())
    V[w-w0].append(v)
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(1,len(V[i])):
        V[i][j] = V[i][j-1]+V[i][j]
    V[i].insert(0,0)
    V[i].append(0)

ans = 0
for i in range(len(V[0])):
    wi = w0*i
    if wi > W:
        break
    vi = V[0][i]
    for j in range(len(V[1])):
        wj = wi + (w0+1)*j
        if wj > W:
            break
        vj = vi + V[1][j]
        for k in range(len(V[2])):
            wk = wj + (w0+2)*k
            if wk > W:
                break
            vk = vj + V[2][k]

            l = min((W-wk)//(w0+3), len(V[3])-1)
            v = vk + V[3][l]
            ans = max(ans, v)
print(ans)

Solution (Python):
from itertools import accumulate
N,W = map(int,input().split())

w0,v0 = map(int,input().split())
W0,W1,W2,W3 = [],[],[],[]
W0.append(v0)
for i in range(1,N):
    w,v = map(int,input().split())
    if w == w0:
        W0.append(v)
    elif w == w0+1:
        W1.append(v)
    elif w == w0+2:
        W2.append(v)
    else:
        W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)
V0 = [0]+list(accumulate(W0))
V1 = [0]+list(accumulate(W1))
V2 = [0]+list(accumulate(W2))
V3 = [0]+list(accumulate(W3))

Ans = 0
for i0 in range(len(V0)):
    for i1 in range(len(V1)):
        for i2 in range(len(V2)):
            for i3 in range(len(V3)):
                if w0*i0 + (w0+1)*i1 + (w0+2)*i2 + (w0+3)*i3 <= W:
                    Ans = max(Ans,V0[i0]+V1[i1]+V2[i2]+V3[i3])

print(Ans)

Solution (Python):
n,w = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
x,y,z,num,ans = sorted(x)[::-1],[0,0,0,0],[[0] for i in range(4)],x[0][0],0
for i,j in x:
	y[i-num] += 1
	z[i-num].append(z[i-num][-1]+j)
for i1 in range(y[0]+1):
	for i2 in range(y[1]+1):
		for i3 in range(y[2]+1):
			for i4 in range(y[3]+1):
				if (i1+i2+i3+i4)*num+i2+2*i3+3*i4>w: break
				else: ans = max(ans,z[0][i1]+z[1][i2]+z[2][i3]+z[3][i4])
print(ans)

Solution (Python):
from itertools import accumulate

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

W0=[]
W1=[]
W2=[]
W3=[]

w,v=map(int,input().split())
W0.append(v)

for i in range(1,N):
  a,b=map(int,input().split())
  if a-w==0:
    W0.append(b)
  elif a-w==1:
    W1.append(b)
  elif a-w==2:
    W2.append(b)
  else:
    W3.append(b)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)
W0=list(accumulate(W0))
W0=[0]+W0
W1=list(accumulate(W1))
W1=[0]+W1
W2=list(accumulate(W2))
W2=[0]+W2
W3=list(accumulate(W3))
W3=[0]+W3

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

Solution (Python):
N,W = map(int,input().split())
w_in, v = map(int,input().split())
table = [[] for i in range(4)]
table[0].append(v)
for i in range(N-1):
    w, v = map(int,input().split())
    table[w-w_in].append(v)
for i in range(4):
    table[i].sort(reverse=True)
    for j in range(len(table[i])-1):
            table[i][j+1] += table[i][j]
    table[i].insert(0,0)
ans = 0
for i in range(len(table[0])):
    for j in range(len(table[1])):
        for k in range(len(table[2])):
            for l in range(len(table[3])):
                if w_in*i+(w_in+1)*j+(w_in+2)*k+(w_in+3)*l <= W:
                    ans = max(ans, table[0][i]+table[1][j]+table[2][k]+table[3][l])
print(ans)

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

for wi, vi in wv:
    plus = wi - standard
    v[plus].append(vi)

for i in range(4):
    v[i].sort(reverse=True)
    for j in range(len(v[i])-1):
        v[i][j+1] = v[i][j] + v[i][j+1]
    v[i].insert(0, 0)

ans = 0
for a in range(len(v[0])):
    for b in range(len(v[1])):
        for c in range(len(v[2])):
            for d in range(len(v[3])):
                if standard*a + (standard+1)*b + (standard+2)*c + (standard+3)*d > W:
                    continue
                else:
                    ans = max(ans, v[0][a]+v[1][b]+v[2][c]+v[3][d])
print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,w]=i2()
a=[]
dp=[[-1 for j in range(100400)]for i in range(n+1)]
dp[0][0]=0
for i in range(n):
 a.append(i2())
b=a[0][0]
c=0
for i in range(1,n+1):
 for j in range(100400):
   dp[i][j]=max(dp[i][j],dp[i-1][j])
   k1=j//1000
   k2=j%1000
   if k1*b+k2<=w and j-1000-a[i-1][0]+b>=0 and dp[i-1][j-1000-a[i-1][0]+b]>=0:
     if dp[i][j]<dp[i-1][j-1000-a[i-1][0]+b]+a[i-1][1]:
        dp[i][j]=dp[i-1][j-1000-a[i-1][0]+b]+a[i-1][1]

   if c<dp[i][j]:
     c=dp[i][j]
     
print(c)

Solution (Python):

"""
https://abc060.contest.atcoder.jp/tasks/arc073_b

"""
import sys
from sys import stdin
input = stdin.readline


def normal_dp(items, N, W):
    dp = [[0] * (W+1) for _ in range(N+1)]

    for y in range(1, N+1):
        w = items[y-1][0]
        v = items[y-1][1]
        for x in range(1, W+1):
            if x >= w:
                dp[y][x] = max(dp[y-1][x-w] + v, dp[y-1][x])
            else:
                dp[y][x] = dp[y-1][x]
    return dp[-1][-1]


def solve(items, N, W):
    items.sort(reverse=True)

    c_items = [[] for _ in range(4)] 
    min_w = items[-1][0]
    for w, v in items:
        c_items[w - min_w].append(v)
    for l in c_items:
        l.append(0)

    
    accumulated_v = [[0] for _ in range(4)]
    for i in range(4):
        for j, v in enumerate(c_items[i], start=1):
            accumulated_v[i].append(accumulated_v[i][-1] + v)

    total_values = []
    for iw0 in range(len(c_items[0])):
        for iw1 in range(len(c_items[1])):
            for iw2 in range(len(c_items[2])):
                for iw3 in range(len(c_items[3])):
                    total_w = (iw0 * min_w) + (iw1 * (min_w+1)) + (iw2 * (min_w+2)) + (iw3 * (min_w+3))
                    if total_w <= W:
                        total_v = accumulated_v[0][iw0] + accumulated_v[1][iw1] + accumulated_v[2][iw2] + accumulated_v[3][iw3]
                        total_values.append(total_v)
    return max(total_values)



def main(args):
    items = []
    N, W = map(int, input().split())
    for _ in range(N):
        w, v = map(int, input().split())
        items.append([w, v])
    items.sort()
    ans = solve(items, N, W)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
def d_SimpleKnapsack(N, W, T):
    from collections import defaultdict
    
    
    dp = defaultdict(int)
    dp[0] = 0  
    for w, v in T:
        for nw, nv in list(dp.items()):
            
            
            
            if nw + w <= W:
                dp[nw + w] = max(dp[nw + w], nv + v)
    return max(dp.values())

N,W = [int(i) for i in input().split()]
T = [[int(i) for i in input().split()] for j in range(N)]
print(d_SimpleKnapsack(N, W, T))

Solution (Python):
N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
minW = min(w)
for i in range(N):
    w[i] -= minW
MAX_W = 3 * 100
MAX_V = int(1e9)
INF = MAX_V + 2
dp = [[-INF] * (MAX_W + 10) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_W, -1, -1):
        for k in range(N-1, -1, -1):
            dp[k+1][j+w[i]] = max((dp[k+1][j+w[i]], dp[k][j] + v[i]))

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

print(ans)

Solution (Python):
from collections import defaultdict
N,W=map(int,raw_input().split())
wv=[]

for i in range(N):
	w,v=map(int,raw_input().split())
	wv.append((w,v))


dp=defaultdict(lambda: 0)	
dp[0]=0

for w1,v1 in wv:
	d=dp.copy()
	for w,v in dp.items():
		dp[w+w1]=max( dp[w+w1], d[w]+v1 )


l1=filter(lambda x:x[0]<=W , dp.items())
print sorted(l1, key=lambda x: x[1],reverse=True)[0][1]

Solution (Python):
from collections import defaultdict
N,W=map(int,raw_input().split())

a=defaultdict(lambda:[])
for i in range(N):
	w,v=map(int,raw_input().split())
	a[w]=a[w]+[v]

for i,j in a.items():
	a[i]=sorted(j,reverse=True)



lst=[]
for i,j in a.items():
	lst.append( (i,len(j)) )

max_val=0
if len(lst)==1:
	w1=lst[0][0]
	c1=lst[0][1]
	for i in range(c1+1):
		if i*w1<=W:
			max_val=max(max_val, sum(a[w1][:i]))

elif len(lst)==2:
	w1=lst[0][0]; w2=lst[1][0]
	c1=lst[0][1]; c2=lst[1][1]
	for i in range(c1+1):
		for j in range(c2+1):
				if i*w1+j*w2<=W:
					max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j]))

elif len(lst)==3:
	w1=lst[0][0]; w2=lst[1][0]; w3=lst[2][0]
	c1=lst[0][1]; c2=lst[1][1]; c3=lst[2][1]
	for i in range(c1+1):
		for j in range(c2+1):
			for k in range(c3+1):
				if i*w1+j*w2+k*w3<=W:
					max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j])+sum(a[w3][:k]))

elif len(lst)==4:
	w1=lst[0][0]; w2=lst[1][0]; w3=lst[2][0]; w4=lst[3][0]
	c1=lst[0][1]; c2=lst[1][1]; c3=lst[2][1]; c4=lst[3][1]
	for i in range(c1+1):
		for j in range(c2+1):
			for k in range(c3+1):
				for m in range(c4+1):
					if i*w1+j*w2+k*w3+m*w4<=W:
						max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j])+sum(a[w3][:k])+sum(a[w4][:m]))

print max_val

Solution (Python):
import itertools

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

minW = items[0][0]
arrVs = [[] for i in range(4)]
for w, v in items:
    arrVs[w - minW].append(v)

acc = [[] for i in range(4)]
for i, arrV in enumerate(arrVs):
    arrV.sort(reverse=True)
    acc[i] = [0] + list(itertools.accumulate(arrV))

num = [range(len(acc[i])) for i in range(4)]

ans = 0
for n in itertools.product(num[0], num[1], num[2], num[3]):
    w = sum([n[i] * (minW + i) for i in range(4)])
    v = sum([acc[i][n[i]] for i in range(4)])
    if w <= W:
        ans = max(ans, v)

print(ans)

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

memo = [{} for i in range(N + 1)]

memo[0] = {0: 0}
for i, (wi, vi) in enumerate(items):
    for w, v in memo[i].items():

        if w + wi <= W:
            memo[i + 1][w + wi] = max(memo[i + 1].get(w + wi, 0), v + vi)

        memo[i + 1][w] = max(memo[i + 1].get(w, 0), v)

print(max(memo[N].values()))

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

w0 = items[0][0]
sizeX = min(W, sum([items[i][0] for i in range(N)])) // w0 + 1
sizeY = min(w0, 3 * (N - 1) + 1)
memo = [[[-1 for y in range(sizeY)] for x in range(sizeX)] for i in range(N + 1)]

memo[0][0][0] = 0
for i, (wi, vi) in enumerate(items):
    for x in range(sizeX):
        for y in range(sizeY):
            if memo[i][x][y] == -1: continue

            wn = w0 * x + y + wi
            if wn <= W:
                memo[i + 1][wn // w0][wn % w0] = memo[i][x][y] + vi

            memo[i + 1][x][y] = max(memo[i + 1][x][y], memo[i][x][y])

print(max(map(max, [memo[N][x] for x in range(sizeX)])))

Solution (Python):
N, W = [int(n) for n in input().split()]

values = [[] for n in range(4)]
w, v = [int(n) for n in input().split()]
w_0 = w
values[0].append(v)

sum_values = [[0] for n in range(4)]


for i in range(1, N):
  w, v = [int(n) for n in input().split()]
  values[w-w_0].append(v)

for i in range(4):
  values[i].sort(reverse=True)
  s = 0
  for j in range(len(values[i])):
    s += values[i][j]
    sum_values[i].append(s)

res = 0
for i in range(len(values[0])+1):
  for j in range(len(values[1])+1):
    for k in range(len(values[2])+1):
      for l in range(len(values[3])+1):
        if (i*w_0 + j*(w_0+1) + k*(w_0+2) + l*(w_0+3))<=W:
          res = max(res, sum_values[0][i]+sum_values[1][j]+sum_values[2][k]+sum_values[3][l])


print(res)

Solution (Python):
n,w=map(int,input().split())
dic=[[],[],[],[]]
a,b=map(int,input().split())
dic[0].append(b)
p=a
v=[1,0,0,0]
for i in range(n-1):
    a,b=map(int,input().split())
    dic[a-p].append(b)
    v[a-p]+=1
for i in range(4):
    dic[i]=sorted(dic[i],reverse=True)
    for j in range(1,v[i]):
        dic[i][j]=dic[i][j]+dic[i][j-1]
    dic[i].insert(0,0)
max_v=0
for i in range(v[0]+1):
    for j in range(v[1]+1):
        for k in range(v[2]+1):
            for l in range(v[3]+1):
                if i*p+j*(p+1)+k*(p+2)+l*(p+3)<=w:
                    max_v=max(max_v,dic[0][i]+dic[1][j]+dic[2][k]+dic[3][l])
print(max_v)

Solution (Python):
import sys
N,W = map(int, raw_input().split())
src = []
wmax = vmax = 0
for i in range(N):
  w,v = map(int, raw_input().split())
  src.append((w,v))
  wmax += w
  vmax += v
w1 = src[0][0]

if w1 > W:
  print(0)
  sys.exit()
if wmax <= W:
  print(vmax)
  sys.exit()

wend = 3*N+1
dp = [[0 for w in range(wend)] for n in range(N+1)]
for i in range(N):
  wi,vi = src[i]
  wi -= w1 
  maxn = min(N,i+1)
  for n in reversed(range(1,maxn+1)):
    for w in range(wi,wend):
      dp[n][w] = max(dp[n][w], dp[n-1][w-wi] + vi)

ans = 0
for n in range(1,N+1):
  remain = W - w1*n
  if remain < 0: break
  w = min(remain, wend-1)
  ans = max(ans, dp[n][w])

print(ans)

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

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

print(nap(0, W))