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:
import sys

def solve():
    N, W = map(int, input().split())
    v = [[] for i in range(4)]

    for i in range(N):
        wi, vi = map(int, input().split())

        if i == 0:
            base = wi
            v[0].append(vi)
        else:
            v[wi - base].append(vi)

    for i in range(4):
        v[i].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):
                    w = base*i + (base + 1)*j + (base + 2)*k + (base + 3)*l

                    if w > W:
                        continue

                    kakaku = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])

                    ans = max(ans, kakaku)

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    N, W = map(int, input().split())
    v = [[] for i in range(4)]

    for i in range(N):
        wi, vi = map(int, input().split())

        if i == 0:
            base = wi
            v[0].append(vi)
        else:
            v[wi - base].append(vi)

    for i in range(4):
        v[i].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):
                w = base*i + (base + 1)*j + (base + 2)*k

                if w > W:
                    continue

                l = (W - w) // (base + 3)

                kakaku = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])

                ans = max(ans, kakaku)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def solve(N, W, w_v):
    memo = collections.defaultdict(int)
    memo[0] = 0
    for w, v in w_v:
        for w_memo, v_memo in sorted(list(memo.items()), key=lambda x: -x[0]):
            if w + w_memo > W:
                continue
            if memo[w + w_memo] < v_memo + v:
                memo[w + w_memo] = v_memo + v

    return max(memo.values())


def main():
    N, W = ILI()
    w_v = IAI(N)
    print(solve(N, W, w_v))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

if 1:
    N,W = map(int, input().split(' '))
    w,v = [],[]
    for i in range(N):
        w_,v_ = map(int, input().split(' '))
        w.append(w_)
        v.append(v_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = sorted(list(idxs))
idx_dict = {idx:i for i,idx in enumerate(idxs)}

dp = [[0 for j in range(len(idxs))] for i in range(N+1)]

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            try:
                dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
            except:
                dp[i+1][j] = dp[i][j]
        
print(max([max(dp_) for dp_ in dp]))

Submission status: Accepted

Solution code:
import collections
import functools

class memoized(object):
    def __init__(self, func):
       self.func = func
       self.cache = {}

    def __call__(self, *args):
       if not isinstance(args, collections.Hashable):
          return self.func(*args)

       if args in self.cache:
          return self.cache[args]

       else:
          value = self.func(*args)
          self.cache[args] = value
          return value

    def __repr__(self):
       return self.func.__doc__

    def __get__(self, obj, objtype):
       return functools.partial(self.__call__, obj)

def knapsack(items, maxweight):
    @memoized
    def bestvalue(i, j):
        if i == 0: return 0
        value, weight = items[i - 1]
        if weight > j:
            return bestvalue(i - 1, j)
        else:
            return max(bestvalue(i - 1, j),
                       bestvalue(i - 1, j - weight) + value)

    j = maxweight
    result = []
    for i in xrange(len(items), 0, -1):
        if bestvalue(i, j) != bestvalue(i - 1, j):
            result.append(items[i - 1])
            j -= items[i - 1][1]
    result.reverse()
    return bestvalue(len(items), maxweight), result

def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack(items, W)[0]

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
ws = []
vs = []

for i in range(N):
	w, v = map(int, input().split())
	ws.append(w)
	vs.append(v)

w1 = ws[0]
s = 0

for i in range(N):
	ws[i] -= w1
	s += ws[i]

dp = [[[0]*(s+1) for i in range(N+1)] for k in range(N)]
for k in range(N):
	if (k+1)*w1 > W:
		break
	for i in range(1,N+1):
		for j in range(s+1):
			if j >= ws[i-1]:
				dp[k][i][j] = max(dp[k-1][i-1][j-ws[i-1]]+vs[i-1], dp[k][i-1][j])
			else:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j])
			if j > 0:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
ans = 0
for k in range(N):
	if W < (k+1)*w1:
		break
	ans = max(ans, dp[k][N][min(W-(k+1)*w1, s)])
print(ans)
from sys import stderr
print(dp, file=stderr)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)

vss = [[], [], [], []]

for i in range(N):
    ind = ws[i] - ws[0]
    vss[ind].append(vs[i])

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

dic = {}

# select_S: (a, b, c, d)


def rec(vss, tmp_W, tmp_V, select_S):
    # print(select_S)
    for i in range(4):
        if len(vss[i]) == 0:
            continue
        new_tmp_W = tmp_W + ws[0] + i
        if new_tmp_W > W:
            continue
        new_tmp_V = tmp_V + vss[i][0]
        new_vss = list(vss)
        new_vss[i] = new_vss[i][1:]

        new_select_S = [select_S[j] for j in range(4)]
        new_select_S[i] += 1
        new_select_S = tuple(new_select_S)
        if new_select_S in dic:
            continue

        dic[new_select_S] = new_tmp_V
        rec(new_vss, new_tmp_W, new_tmp_V, new_select_S)


rec(vss, 0, 0, (0, 0, 0, 0))
ans = sorted(list(dic.values()), reverse=True)
if len(ans) == 0:
    print(0)
else:
    print(ans[0])

Submission status: Accepted

Solution code:
# D
import numpy as np
N, W = map(int, input().split())
v_list_0 = []
v_list_1 = []
v_list_2 = []
v_list_3 = []

w0, v0 = map(int, input().split())
v_list_0.append(v0)

for i in range(1, N):
    w, v = map(int, input().split())
    if w == w0:
        v_list_0.append(v)
    elif w == w0+1:
        v_list_1.append(v)
    elif w == w0+2:
        v_list_2.append(v)
    else:
        v_list_3.append(v)

# best weight
vn0 = np.cumsum([0] + sorted(v_list_0, reverse=True))
vn1 = np.cumsum([0] + sorted(v_list_1, reverse=True))
vn2 = np.cumsum([0] + sorted(v_list_2, reverse=True))
vn3 = np.cumsum([0] + sorted(v_list_3, reverse=True))

# find best n0, n1, n2, n3
vmax = 0
n3_max = min(len(v_list_3), W//(w0+3))
for n3 in range(n3_max+1):
    n2_max = min(len(v_list_2), (W - (n3*(w0+3)))//(w0+2))
    for n2 in range(n2_max+1):
        n1_max = min(len(v_list_1), (W - (n3*(w0+3) + n2*(w0+2)))//(w0+1))
        for n1 in range(n1_max+1):
            n0_max = min(len(v_list_0), (W - (n3*(w0+3) + n2*(w0+2) + n1*(w0+1)))//(w0))
            vnow = vn3[n3] + vn2[n2] + vn1[n1] + vn0[n0_max]
            if vnow > vmax:
                vmax = vnow
print(vmax)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import *
from functools import reduce,partial
from time import time
from pprint import pprint

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

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

p = 1000000000 + 7

n,w = readln()
f = [sequence(303) for i in range(0,n+1)]
w1 = -1
f[0] = sequence(303,constant(-1000))
f[0][0] = 0
for i in range(0,n):
    g = [row [:] for row in f]
    wi,vi = readln()
    if w1 < 0 : w1 = wi
    wi -= w1
    for count in range(0,i+1):
        for weight in range(0,303 - wi):
            f[count + 1][weight + wi] = max(
                f[count + 1][weight + wi],
                g[count][weight] + vi)
ans = 0
for count in range(0,n+1):
    for weight in range(0,303):
        if weight + count * w1 <= w:
            ans = max(ans,f[count][weight])
print(ans)

Submission status: Accepted

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

p = [[] for i in range(4)]
for i in range(N):
    ww,v = map(int, input().split())
    if i == 0:
        w0 = ww
    p[ww % 4].append(v)
w = [0 for i in range(4)]
v = [0 for i in range(4)]
for i in range(4):
    p[i].sort(reverse=True)
    w[(w0+i)%4] = w0+i
maxv = 0
lens = [len(p[i])+1 for i in range(4)]
for i in range(lens[0]):
    sumw = w[0] * i
    if sumw > W:
        break
    v[0] = sum(p[0][:i])
    maxv = max(maxv, sum(v))
    for j in range(lens[1]):
        sumw = w[0] * i + w[1]*j
        if sumw > W:
            break
        v[1] = sum(p[1][:j])
        maxv = max(maxv, sum(v))
        for k in range(lens[2]):
            sumw = w[0] * i + w[1]*j + w[2]*k
            if sumw > W:
                break
            v[2] = sum(p[2][:k])
            maxv = max(maxv, sum(v))
            for l in range(lens[3]):
                sumw = w[0] * i + w[1]*j + w[2]*k + w[3]*l
                if sumw > W:
                    break
                v[3] = sum(p[3][:l])
                maxv = max(maxv, sum(v))
            v[3] = 0
        v[2] = 0
        v[3] = 0
    v[1] = 0
    v[2] = 0
    v[3] = 0    
v[0] = 0
print(maxv)

Submission status: Accepted

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

memo = {i:{} for i in range(N)}

def r(i, g):
    global memo
    if i == N:
        return 0
    elif g in memo[i]:
        return memo[i][g]
    elif g < w[i]:
        a = r(i + 1, g)
    else:
        a = max(r(i + 1, g - w[i]) + v[i], r(i + 1, g))
    
    memo[i][g] = a
    return a

print(r(0, W))

Submission status: Accepted

Solution code:
import sys

inf = 1 << 32

def solve():
    N, W = map(int, input().split())
    ws = []
    vs = []

    for i in range(N):
        wi, vi = map(int, input().split())
        ws.append(wi)
        vs.append(vi)

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

    dp[0][0][0] = 0

    for i in range(N):
        for j in range(N + 1):
            for k in range(3*N + 1):
                dp[i + 1][j][k] = dp[i][j][k]

                if j - 1 >= 0 and k - (ws[i] - ws[0]) >= 0:
                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - (ws[i] - ws[0])] + vs[i])

    ans = 0

    for j in range(N + 1):
        for k in range(3*N + 1):
            if ws[0]*j + k <= W:
                ans = max(ans, dp[N][j][k])

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n, W = [int(_) for _ in raw_input().split()]

wvs = [[int(_) for _ in raw_input().split()] for i in xrange(n)]

p = {0: 0}

for w, v in wvs:
    for d, dv in p.items():
        p[d + w] = max(p.get(d + w, 0), dv + v)
    m = -1
    for d, dv in sorted(p.items()):
        if dv <= m:
            del p[d]
            continue
        m = max(m, dv)

ans = 0
for d, dv in sorted(p.items()):
    if d > W:
        break
    ans = dv

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3


import functools
import sys


MAXSIZE = 2 ** 16
REC_LIMIT = 10000


def main():
    N, W = (int(x) for x in input().split())
    w = [-1 for _ in range(N)]
    v = [-1 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = (int(x) for x in input().split())

    @functools.lru_cache(maxsize=MAXSIZE)
    def rec(i, j):
        if i == N:
            res = 0
        elif j < w[i]:
            res = rec(i + 1, j)
        else:
            res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
        return res
    ans = rec(0, W)
    print(ans)


if __name__ == '__main__':
    sys.setrecursionlimit(REC_LIMIT)
    main()

Submission status: Accepted

Solution code:
n,W=map(int,raw_input().split())
wv=[map(int,raw_input().split()) for _ in xrange(n)]
diff=[]
for i in xrange(n):
    diff.append(wv[i][0]-wv[0][0])
dp=[[[0]*301 for _ in xrange(n+1)] for _ in xrange(n+1)]
for i in xrange(n):
    w,v=wv[i]
    for j in xrange(i+1):
        for k in xrange(301):
            if k-diff[i]<0:
                dp[i+1][j+1][k]=dp[i][j+1][k]
            else:
                dp[i+1][j+1][k]=max(dp[i][j+1][k],dp[i][j][k-diff[i]]+v)
ans=0
for j in xrange(n+1):
    for k in xrange(301):
        if j*wv[0][0]+k<=W:
            ans=max(ans,dp[n][j][k])
print ans

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ans = 0
memo = {0: 0}
for i in range(N):
    w = ws[i]
    v = vs[i]
    tmp = {}
    for w0, v0 in memo.items():
        if w0 + w <= W:
            ans = max(ans, v0 + v)
            if w0 + w in tmp:
                tmp[w0 + w] = max(tmp[w0 + w], v0 + v)
            else:
                tmp[w0 + w] = v0 + v
    for w0, v0 in tmp.items():
        if w0 in memo:
            memo[w0] = max(memo[w0], tmp[w0])
        else:
            memo[w0] = tmp[w0]
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,W = LI()
    a = [LI() for _ in range(n)]
    r = 0
    d = collections.defaultdict(int)
    d[0] = 0
    for w,v in a:
        for e,f in sorted(list(d.items()), key=lambda x: -x[0]):
            if e+w > W:
                continue
            if d[e+w] < d[e] + v:
                d[e+w] = d[e] + v

    return max(d.values())


print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, W, WV):
    vl = {}
    vl[WV[0][0]] = list()
    vl[WV[0][0]+1] = list()
    vl[WV[0][0]+2] = list()
    vl[WV[0][0]+3] = list()
    for w, v in WV:
        vl[w].append(v)

    for v in vl.values():
        v.sort(reverse=True)
        v.insert(0, 0)

    wl = vl.keys()
    wi, wj, wk = wl
    ans = 0
    vis = 0
    for i, vi in enumerate(vl[wi]):
        if wi * i > W:
            break
        vis += vi
        vjs = 0
        for j, vj in enumerate(vl[wj]):
            if wi * i + wj * j > W:
                break
            vjs += vj
            vks = 0
            for k, vk in enumerate(vl[wk]):
                if wi*i + wj*j + wk*k> W:
                    break
                vks += vk
                ans = max(ans, vis+vjs+vks)
    return ans





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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, W, WV):
    vl = {}
    vl[WV[0][0]] = list()
    vl[WV[0][0]+1] = list()
    vl[WV[0][0]+2] = list()
    for w, v in WV:
        vl[w].append(v)

    for v in vl.values():
        v.sort(reverse=True)
        v.insert(0, 0)
    wl = vl.keys()
    wi, wj, wk = wl
    ans = 0
    vis = 0
    for i, vi in enumerate(vl[wi]):
        if wi * i > W:
            break
        vis += vi
        vjs = 0
        for j, vj in enumerate(vl[wj]):
            if wi * i + wj * j > W:
                break
            vjs += vj
            vks = 0
            for k, vk in enumerate(vl[wk]):
                if wi*i + wj*j + wk*k> W:
                    break
                vks += vk
                ans = max(ans, vis+vjs+vks)
    return ans





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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def solve():
    N, W = getList()
    MI = 100
    MJ = 300
    sina = []
    w, v = getList()
    w1 = w
    v1 = v
    # sina.append((w ,v))
    for i in range(N-1):
        w, v = getList()
        sina.append((w - w1, v))

    dp = [-1 for i in range(MI*MJ+2)]
    dp[0] = 0
    dp[MJ] = v1
    for w, v in sina:
        # print(w,v)
        nxt = [-1 for i in range(MI*MJ+2)]
        for i in range(MI):
            for j in range(MJ):
                cur = dp[i*MJ + j]
                if cur != -1:
                    if nxt[i * MJ + j] < cur:
                        nxt[i * MJ + j] = cur
                    # print(cur)
                    # print(nxt[(i+1) * MJ + j + w])
                    if nxt[(i+1) * MJ + j + w] < cur + v:
                        nxt[(i + 1) * MJ + j + w] = cur + v
                        # print("update")

        dp = nxt
        # for i in range(MI):
        #     print(dp[i * MJ:i * MJ + MJ - 1])

    ans = 0
    for i in range(MI):
        for j in range(MJ):
            # print(i, j, dp[i * MJ + j])
            if w1 * i + j <= W:

                if dp[i*MJ + j] > ans:
                    # print(dp[i+MJ + j])
                    ans = dp[i * MJ + j]

    print(ans)






def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, W = map(int, input().split())
    d = defaultdict(list)
    w, v = map(int, input().split())
    w1 = w
    d[w].append(v)
    for _ in range(1, N):
        w, v = map(int, input().split())
        d[w].append(v)

    cumsum = defaultdict(list)
    L = defaultdict(int)
    for k, v in d.items():
        d[k].sort(reverse=True)
        c = np.cumsum(d[w])
        cumsum[w] = c
        L[k - w1] = len(d[w])

    ans = 0
    for i in range(L[0] + 1):
        if i != 0:
            v1 = cumsum[w1][i - 1]
        else:
            v1 = 0
        for j in range(L[1] + 1):
            if j != 0:
                v2 = v1 + cumsum[w1 + 1][j - 1]
            else:
                v2 = v1
            for k in range(L[2] + 1):
                if k != 0:
                    v3 = v2 + cumsum[w1 + 2][k - 1]
                else:
                    v3 = v2
                for l in range(L[3] + 1):
                    w = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                    if w > W:
                        continue

                    if l != 0:
                        v4 = v3 + cumsum[w1 + 3][l - 1]
                    else:
                        v4 = v3

                    if v4 > ans:
                        ans = v4

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, W = map(int, input().split())
    d = defaultdict(list)
    w, v = map(int, input().split())
    w1 = w
    d[w].append(v)
    for _ in range(1, N):
        w, v = map(int, input().split())
        d[w].append(v)

    cumsum = dict()
    L = dict()
    for i in range(4):
        w = w1 + i
        d[w].sort(reverse=True)
        c = np.cumsum(d[w])
        cumsum[w] = c
        L[i] = len(d[w])

    ans = 0
    for i in range(L[0] + 1):
        if i != 0:
            v1 = cumsum[w1][i - 1]
        else:
            v1 = 0
        for j in range(L[1] + 1):
            if j != 0:
                v2 = v1 + cumsum[w1 + 1][j - 1]
            else:
                v2 = v1
            for k in range(L[2] + 1):
                if k != 0:
                    v3 = v2 + cumsum[w1 + 2][k - 1]
                else:
                    v3 = v2
                for l in range(L[3] + 1):
                    w = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                    if w > W:
                        continue

                    if l != 0:
                        v4 = v3 + cumsum[w1 + 3][l - 1]
                    else:
                        v4 = v3

                    if v4 > ans:
                        ans = v4

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import collections
N, W = map(int, input().split())
wv = collections.defaultdict(list)
w = 0
for i in range(N):
    a, b = map(int, input().split())
    wv[a].append(b)
    if i == 0:
        w = a
s = [[0]*(len(wv[w+i])+1) for i in range(4)]

for i in range(4):
    wv[w + i].sort(reverse=True)
    for j, x in enumerate(wv[w + i]):
        s[i][j+1] = s[i][j] + x
ans = 0
L = len(wv[3])
for i in range(min(len(wv[w]), N)+1):
    tmp1 = s[0][i]
    weight1 = w * i
    if weight1 > W:
        break
    for j in range(min(len(wv[w+1])+1, N+1 - i)):

        tmp2 = tmp1 + s[1][j]
        weight2 = weight1 + (w+1)*j
        if weight2 > W:
            break
        for k in range(min(len(wv[w+2])+1, N+1 - i - j)):
            tmp3 = tmp2 + s[2][k]
            weight3 = weight2 + (w+2)*k
            if weight3 > W:
                break
            d = W - weight3

            ans = max(ans, tmp3 + s[3][min(L, d//(w+3))])
print(ans)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))
dp={}
dp[0]=0
for w,v in WV:
    for i in JinA:
        if i+w>w:
            continue 
        temp=dp[i]
        try:
            use=dp[i+w]
            dp[i+w]+=max(temp+v-use,0)
        except:
            dp[i+w]=temp+v 
    
ans=[]
for i in dp:
    heappush(ans,-dp[i])

print(-heappop(ans))

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))

dp=[0]*(w*2)
for w,v in WV:
    for i in range(w+1):
        try: dp[i]=max(dp[i],dp[i-w]+v)
        except:
            dp[i]=dp[i]


print(max(dp[:w+1]))

Submission status: Runtime Error

Solution code:
# AtCoder Regular Contest 073
# D - Simple Knapsack
# https://atcoder.jp/contests/arc073/tasks/arc073_b
from itertools import combinations_with_replacement, accumulate
N, W, *A = map(int, open(0).read().split())
w0 = A[0]
T = [[] for _ in [0]*4]
M = [0]*4

for w, v in zip(*[iter(A)]*2):
    T[w-w0].append(v)
    M[w-w0] += 1
for t in T:
    t.sort()

acm = [tuple(accumulate(t)) for t in T]


def rec(w=0, k=0, c=()):
    if k == 4:
        C.append(c)
        return
    for i in range(M[k]+1):
        w1 = w + i*(w0+k)
        if w1 > W:
            break
        rec(w1, k+1, (*c, i))


C = []
rec()

ans = 0
for c in C:
    ans = max(ans, sum(acm[i][n-1] if n > 0 else 0 for i, n in enumerate(c)))

print(ans)

Submission status: Runtime Error

Solution code:
n,l = map(int,input().split())
dp = []
for i in range(n+1):
    dp.append([0]*(l+1))
for i in range(1, n+1):
    w,v = map(int,input().split())
    for j in range(l+1):
        if l < w:
            continue
        elif j < w <= l:
            dp[i][j] = dp[i-1][j]
        elif w <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
print(max(dp[n]))

Submission status: Runtime Error

Solution code:
n,l = map(int,input().split())
dp = []
for i in range(n+1):
    dp.append([0]*(l+1))
for i in range(1, n+1):
    w,v = map(int,input().split())
    for j in range(l+1):
        if l < w:
            continue
        elif j < w <= l:
            dp[i][j] = dp[i-1][j]
        elif w <= j <= l:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
print(dp[n][l])

Submission status: Runtime Error

Solution code:
n,l = map(int,input().split())
dp = []
for i in range(n+1):
    dp.append([0]*(l+1))
for i in range(1, n+1):
    w,v = map(int,input().split())
    for j in range(l+1):
        if l < w:
            pass
        elif j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
print(dp[n][l])

Submission status: Runtime Error

Solution code:
n,l = map(int,input().split())
dp = []
for i in range(n+1):
    dp.append([0]*(l+1))
for i in range(1, n+1):
    w,v = map(int,input().split())
    for j in range(l+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
print(dp[n][l])