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.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Accepted

Solution code:
#00:58
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)
#print(wv)
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)
#print(cum)
#print(z)
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(can)
print(max(can))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    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): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Simple Knapsack
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]
# print(dic)

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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[i][j]…荷物の個数がiで、端数の合計がjのときの価値の最大値
    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)
    #p2D(dp)
    print(max(max(row) for row in dp))

main()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
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)
#print(x)
#print(w0)
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

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

print(ma)

Submission status: Accepted

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

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

print(ma)

Submission status: Accepted

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

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

print(ma)

Submission status: Accepted

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

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

print(ma)

Submission status: Accepted

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

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

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
x_sub=[[v_sub],[],[],[]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x_sub[z].append(v_sub)
for i in range(4):
    x_sub[i].sort(key=lambda x:-x)
#print(x_sub)
x=[[0],[0],[0],[0]]
for i in range(4):
    for j in x_sub[i]:
        k=j+x[i][-1]
        x[i].append(k)
#print(x)
#print(w0)
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)

Submission status: Accepted

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

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

print(ma)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=itemgetter(1),reverse=True)#reverse
wv.sort(key=itemgetter(0))
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    m=min(d//w0,l0-1)
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][m]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        if w-i*(w0+3)-j*(w0+2)>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    d=w-i*(w0+3)
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
                    ma=max(ma,ma_sub)
                else:
                    break
        else:
            break

print(ma)