Submission #2895413

---

Source Code Expand

from itertools import accumulate

N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
    
    
w1 = WV[0][0]
w1p0 = [0]
w1p1 = [0]
w1p2 = [0]
w1p3 = [0]
for w, v in WV:
    if w == w1:
        w1p0.append(v)
    elif w == w1+1:
        w1p1.append(v)
    elif w == w1+2:
        w1p2.append(v)
    else:
        w1p3.append(v)
        
w1p0.sort()
w1p1.sort()
w1p2.sort()
w1p3.sort()

w1p0sum = list(accumulate(w1p0))
w1p1sum = list(accumulate(w1p1))
w1p2sum = list(accumulate(w1p2))
w1p3sum = list(accumulate(w1p3))

ans_cand = [0]
for p0 in range(len(w1p0sum)-1,-1,-1):
    if p0*w1 > W:
        continue
    
    for p1 in range(len(w1p1sum)-1,-1,-1):
        if p0*w1+p1+1*(w1+1) > W:
            continue
        
        for p2 in range(len(w1p2sum)-1,-1,-1):
            if p0*w1+p1*(w1+1)+p2*(w1+2) > W:
                continue
            
            for p3 in range(len(w1p3sum)-1,-1,-1):
                if p0*w1+p1*(w1+1)+p2*(w1+2)+p3*(w1+3) > W:
                    continue
                
                ans_cand.append(w1p0sum[p0]+w1p1sum[p1]\
                                +w1p2sum[p2]+w1p3sum[p3])
                
print(max(ans_cand))

Submission Info

Judge Result