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: Wrong Answer

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):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = 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(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

m = {}
def update(W, wi, vi):
        if wi > W:
                return
        global m
        ks = m.keys()
        a = set()
        for wj in ks:
                wk = wj + wi
                if wk <= W:
                        vk = m[wj] + vi
                        if wk not in m or m[wk] < vk:
                                m[wk] = vk
                                a.add(wk)
        if wi not in m or m[wi] < vi:
                m[wi] = vi
                a.add(wi)
        for wj in a:
                for wk in ks:
                        if wj in m and wk in m and wk > wj and m[wk] <= m[wj]:
                                del(m[wk])

def calc(W, w, v):
        global m
        m = {}
        for i in range(len(w)):
                update(W, w[i], v[i])
        print max(m.values() + [0])

N, W = rdi()
w = []
v = []
for i in range(N):
        wi, vi = rdi()
        w.append(wi)
        v.append(vi)
calc(W, w, v)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]



m = {}
def update(W, wi, vi):
        if wi > W:
                return
        global m
        ks = m.keys()
        a = set()
        for wj in ks:
                wk = wj + wi
                if wk <= W:
                        vk = m[wj] + vi
                        if wk not in m or m[wk] < vk:
                                m[wk] = vk
                                a.add(wk)
        if wi not in m or m[wi] < vi:
                m[wi] = vi
                a.add(wi)
        for wj in a:
                for wk in ks:
                        if wj not in m:
                                break
                        if wk in m and wk > wj and m[wk] <= m[wj]:
                                del(m[wk])
                                break

def calc(W, w, v):
        global m
        m = {}
        for i in range(len(w)):
                update(W, w[i], v[i])
        print max(m.values() + [0])

N, W = rdi()
w = []
v = []
for i in range(N):
        wi, vi = rdi()
        w.append(wi)
        v.append(vi)
calc(W, w, v)

Submission status: Wrong Answer

Solution code:
n, W = map(int, raw_input().split())
w = []
v = []
for _ in xrange(n):
    a, b = map(int, raw_input().split())
    w.append(a)
    v.append(b)
dp = [[0]*n for _ in xrange(W+1)]
for i in xrange(n):
    dp[0][i] = 0
for _ in xrange(w[0], W+1):
    dp[_][0] = v[0]

y = 0
for i in xrange(1, n):
    y += w[0] + 3
    for j in xrange(w[0], min(y, W+1)):
        k = j - w[i]
        if k < 0:
            x = 0
        else:
            x = dp[k][i-1] + v[i]
        if dp[j][i -1] > x:
           x = dp[j][i-1]
        dp[j][i] = x
        # for _ in xrange(W+1):
        #     print dp[_]
        # print ""
print dp[-1][-1]

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
v = [[] for i in range(4)]  # w1+x
w1 = -1

for i in range(N):
    a, b = map(int, input().split())
    if i == 0:
        w1 = a
    v[a - w1].append(b)

for i in range(4):
    v[i].reverse()  # 価値の高い順にソート

ret = 0

sum_v = [[] for i in range(4)]  # w1+x
for i in range(4):
    for j in range(len(v[i])+1):
        sum_v[i].append(sum(v[0][0:j]))
# print(sum_v)

for i in range(len(v[0])+1):
    for j in range(len(v[1])+1):
        for k in range(len(v[2])+1):
            for l in range(len(v[3])+1):
                if (i+j+k+l) * w1 + (i*0+j*1+k*2+l*3) > W:
                    continue
                else:
                    ret = max(ret, sum_v[0][i] + sum_v[1][j] + sum_v[2][k] + sum_v[3][l])

print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

m = {}
def update(W, wi, vi):
        if wi > W:
                return
        global m
        ks = m.keys()
        a = set()
        for wj in ks:
                wk = wj + wi
                if wk <= W:
                        vk = m[wj] + vi
                        if wk not in m or m[wk] < vk:
                                m[wk] = vk
                                a.add(wk)
        if wi not in m or m[wi] < vi:
                m[wi] = vi
                a.add(wi)
        for wj in a:
                for wk in ks:
                        if wk in m and wk > wj and m[wk] <= m[wj]:
                                del(m[wk])
                                break

def calc(W, w, v):
        global m
        m = {}
        for i in range(len(w)):
                update(W, w[i], v[i])
        print max(m.values() + [0])

N, W = rdi()
w = []
v = []
for i in range(N):
        wi, vi = rdi()
        w.append(wi)
        v.append(vi)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
v = [[] for i in range(4)]  # w1+x
w1 = -1

for i in range(N):
    a, b = map(int, input().split())
    if i == 0:
        w1 = a
    v[a - w1].append(b)

for i in range(4):
    v[i].reverse()  # 価値の高い順にソート

ret = 0

for i in range(len(v[0])+1):
    for j in range(len(v[1])+1):
        for k in range(len(v[2])+1):
            for l in range(len(v[3])+1):
                if (i+j+k+l) * w1 + (i*0+j*1+k*2+l*3) > W:
                    continue
                else:
                    ret = max(ret, sum(v[0][0:i]) + sum(v[1][0:j]) + sum(v[2][0:k]) + sum(v[3][0:l]))

print(ret)

Submission status: Wrong Answer

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 list(d.items()):
            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: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

MAXDW = 300
INF = 10 ** 12

n, maxw = map(int, input().split())
list_dw = []
list_v = []
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        list_dw.append(0)
    else:
        list_dw.append(w - w0)
    list_v.append(v)


list_maxv = [[[None] * (MAXDW + 1) for _ in range(n + 1)] for _ in range(n + 1)]


def maxv(i, k, dw):
    # item[:i], n of items k
    if i == 0:
        if k == 0 and dw == 0:
            return 0
        else:
            return -INF
    elif k == 0:
        if dw == 0:
            return 0
        else:
            return -INF
    elif dw < 0:
        return -INF
    elif list_maxv[i][k][dw] is not None:
        return list_maxv[i][k][dw]
    else:
        result = max([
            list_v[i - 1] + maxv(i - 1, k - 1, dw - list_dw[i - 1]),
            maxv(i - 1, k, dw),
        ])
        list_maxv[i][k][dw] = result
        return result


m = 0
for k in range(n + 1):
    for dw in range(MAXDW + 1):
        if k * w0 + dw <= maxw:
            m = max(m, maxv(n, k, dw))

print(m)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

MAXDW = 300
INF = 10 ** 12

n, maxw = map(int, input().split())
list_w = []
list_v = []
for i in range(n):
    w, v = map(int, input().split())
    list_w.append(w)
    list_v.append(v)

w0 = list_w[0]
list_dw = []
for w in list_w:
    list_dw.append(w - w0)


list_maxv = [[[None] * (MAXDW + 1) for _ in range(n + 1)] for _ in range(n + 1)]


def maxv(i, k, dw):
    # item[:i], n of items k
    if i == 0:
        if k == 0 and dw == 0:
            return 0
        else:
            return -INF
    elif k == 0:
        if dw == 0:
            return 0
        else:
            return -INF
    elif dw < 0:
        return -INF
    elif list_maxv[i][k][dw] is not None:
        return list_maxv[i][k][dw]
    else:
        result = max(
            list_v[i - 1] + maxv(i - 1, k - 1, dw - list_dw[i - 1]),
            maxv(i - 1, k, dw),
        )
        list_maxv[i][k][dw] = result
        return result


m = 0
for i in range(n + 1):
    for k in range(n + 1):
        for dw in range(MAXDW + 1):
            if k * w0 + dw <= maxw:
                m = max(m, maxv(i, k, dw))

print(m)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import defaultdict
import sys
N_MAX = 100
W_MAX = 10**9
V_MAX = 10**7
INF = 10**10
def main(N, W, items):
    dp = defaultdict(lambda: INF)
    dp[0] = 0
    for i in range(N):
        iw, iv = items[i]
        for v, w in list(dp.items()):
            if w + iw <= W:
                dp[v + iv] = min(dp[v + iv], w + iw)
    print(max(dp.keys()))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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())
    WV = []
    for _ in range(N):
        w, v = map(int, input().split())
        WV.append((w, v))

    # bfs
    # i, weight, value
    q = deque([(-1, 0, 0)])

    ans = 0
    while q:
        i, w, v = q.popleft()

        for j in range(i + 1, N):
            tmp_w = w + WV[j][0]
            if tmp_w > W:
                continue

            tmp_v = v + WV[j][1]
            if tmp_v > ans:
                ans = tmp_v
            q.append((j, tmp_w, tmp_v))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3                                                                                         
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import groupby, product
    wv_list = [list(g) for k, g in groupby(sorted(zip(w, v), key=lambda x:(x[0],-x[1])), key=lambda x:x[0])]
    base_w = wv_list[0][0][0]
    acc_wv = [[0] * (N+1) for _ in range(4)]
    for wv in wv_list:
        i = wv[0][0] - base_w
        for j, (_, v) in enumerate(wv):
            acc_wv[i][j+1] = acc_wv[i][j] + v
    ans = 0
    for i, j, k, l in product(range(N+1), repeat=4):
        if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) > W:
            continue
        ans = max(ans, acc_wv[0][i] + acc_wv[1][j] + acc_wv[2][k] + acc_wv[3][l])
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools                                          
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int                                                                         
    W = int(next(tokens))  # type: int                                                                         
    w = [int()] * (N)  # type: "List[int]"                                                                     
    v = [int()] * (N)  # type: "List[int]"                                                                     
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()                                                                                                    
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import groupby, product
    wv_list = [list(g) for k, g in groupby(sorted(zip(w, v), key=lambda x:(x[0],-x[1])), key=lambda x:x[0])]
    base_w = wv_list[0][0][0]
    acc_wv = [[0] * (N+1) for _ in range(4)]
    for wv in wv_list:
        i = wv[0][0] - base_w
        for j, (_, v) in enumerate(wv):
            acc_wv[i][j+1] = acc_wv[i][j] + v
    ans = 0
    for i, j, k, l in product(range(N+1), repeat=4):
        if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) > W:
            continue
        ans = max(ans, acc_wv[0][i] + acc_wv[1][j] + acc_wv[2][k] + acc_wv[3][l])
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

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

WV = [tuple(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
R = N * 3

dp = [[-10**18] * (R + 1) for _ in range(N + 1)]
dp[0][0] = 0

for w, v in WV:
    w -= W0
    for n in range(N)[::-1]:
        for i in range(R)[::-1]:
            if i + w <= R:
                dp[n + 1][i + w] = max(dp[n + 1][i + w], dp[n][i] + v)

ans = 0
for n in range(N + 1):
    for w in range(R + 1):
        if n * W0 + w <= W:
            ans = max(ans, dp[n][w])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
DP = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    for w in range(W + 1):
        if w >= weight[i]:
            DP[i + 1][w] = max(DP[i][w - weight[i]] + value[i], DP[i][w])
        else:
            DP[i + 1][w] = DP[i][w]

print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

w0 = WV[0][0]
for i in range(N):
    WV[i][0] -= w0

# (i, j, k): i番目まででj個選んで総重量がk以下のときの最大値
dp = defaultdict(lambda: -float("inf"))

# 初期条件
dp[(0, 0, 0)] = 0

# 配るDP
for i, (w, v) in enumerate(WV):
    for j in range(i + 1):
        for k in range(300):
            dp[(i + 1, j, k)] = max(dp[(i + 1, j, k)], dp[(i, j, k)])
            dp[(i + 1, j  + 1, k + w)] = max(dp[(i + 1, j  + 1, k + w)], dp[(i, j, k)] + v)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値(ときどき逆になることがあるので注意)
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  for w in range(1,W+1):
    if w-lb[i][0] >= 0:
      dp[i+1][w] = max(dp[i][w],dp[i][w-lb[i][0]]+lb[i][1]) 
    else:
      dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    w0 = WV[0][0]
    Ws = [w[0] for w in WV]
    Vs = [v[1] for v in WV]
    from collections import defaultdict
    dp = defaultdict(int)
    for i in range(N):
        for j in range(w0, W+1):
            dp[i+1, j] = max(dp[i+1, j], dp[i, j])
            if 0 <= j - Ws[i]:
                dp[i+1, j] = max(dp[i+1, j], dp[i, j - Ws[i]] + Vs[i])
    print(dp[N, W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
inf=float("inf")
dp=[[-inf for _ in range(W+1)] for _ in range(N+1) ] #dp[n][w] 
for i in range(W+1):
  dp[0][i]=0

for i in range(N):
  w,v=map(int,input().split())
  for j in range(W+1):
    if j-w>=0: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
      dp[i+1][j]=max(dp[i][j-w]+v, dp[i][j])
    else: #入る可能性はない
      dp[i+1][j]=dp[i][j]
print(dp[N][W])

Submission status: Time Limit Exceeded

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)
ws_m = [w-ws[0] for w in ws]
# ws_m = [w-min(ws) for w in ws]
"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[0]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(N):
        for j in range(3*N):
            # もらうDP
            # j-wなら、新しくwをナップサックに入れて価値が増えるか見る
            if j-w >= 0:
                dp[i+1][n+1][j] = max(dp[i][n+1][j], dp[i][n][j-w]+v)
            # 追加できない場合は以前の情報を更新
            else:
                dp[i+1][n+1][j] = dp[i][n+1][j]

ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=[]
for w,v in WV:
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1:
            lst.append([w1+w,v1+v])
    lst.append([w,v])

    lst=sorted(lst,key=lambda x:x[0],reverse=True)
    while lst and lst[-1][0]==0:
        lst.pop()

    w,v=lst[-1]
    for i in range(len(lst)-1)[::-1]:
        w1,v1=lst[i]
        if v1<=v:
            lst[i][0]=0
            lst[i][1]=0
        else:
            v1=v
print(max([v for w,v in lst if w<=W]))

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(n)]
w=[b[0] for b in a]
v=[b[1] for b in a]
l=[[0 for q in range(W+1)]for p in range(n+1)]
for r in range(n+1):
    for c in range(W+1):
        if c==0 or r==0:continue
        elif w[r-1]>c:l[r][c]=l[r-1][c]
        else:l[r][c]=max(l[r-1][c],v[r-1]+l[r-1][c-w[r-1]])
print(l[n][W])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,W=LI()
m={}
for i in range(n):
    w,v=LI()
    if w in m:
        m[w].append(v)
    else:
        m[w]=[v]

a=[]
for i,j in m.items():
    sj=sorted(j)[::-1]
    aj=[sum(j)]
    for x in sj:
        aj+=[aj[-1]-x]
    a.append([i,len(j),aj])

cnt0=[0]*len(m.items())
weights=[i for i,j,k in a]

ans=0
sys.setrecursionlimit(10**6)

v=[False]*102**4
def dfs(cnt):
    global ans
    k=sum([cnt[i]*101**i for i in range(len(cnt))])
    if v[k]:return
    v[k]= True
    tot=0
    V=0
    for i in range(len(cnt)):
        tot+=cnt[i]*weights[i]
        if cnt[i]>a[i][1] or tot>W:
            return
        V+=a[i][2][0]-a[i][2][cnt[i]]
    ans=max(ans,V)
    for i in range(len(cnt)):
        l=[cnt[j] + (1 if i==j else 0) for j in range(len(cnt))]
        dfs(l)

dfs(cnt0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,W=LI()
m={}
for i in range(n):
    w,v=LI()
    if w in m:
        m[w].append(v)
    else:
        m[w]=[v]

a=[]
for i,j in m.items():
    sj=sorted(j)[::-1]
    aj=[sum(j)]
    for x in sj:
        aj+=[aj[-1]-x]
    a.append([i,len(j),aj])

cnt0=[0]*len(m.items())
weights=[i for i,j,k in a]

ans=0
sys.setrecursionlimit(10**6)

def dfs(cnt):
    global ans
    tot=0
    V=0
    for i in range(len(cnt)):
        tot+=cnt[i]*weights[i]
        if cnt[i]>a[i][1] or tot>W:
            return
        V+=a[i][2][0]-a[i][2][cnt[i]]
    ans=max(ans,V)
    for i in range(len(cnt)):
        l=[cnt[j] + (1 if i==j else 0) for j in range(len(cnt))]
        dfs(l)

dfs(cnt0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,W=LI()
m={}
for i in range(n):
    w,v=LI()
    if w in m:
        m[w].append(v)
    else:
        m[w]=[v]

a=[]
for i,j in m.items():
    sj=sorted(j)[::-1]
    aj=[sum(j)]
    for x in sj:
        aj+=[aj[-1]-x]
    a.append([i,len(j),aj])

cnt0=[0]*len(m.items())
weights=[i for i,j,k in a]

ans=0
sys.setrecursionlimit(10**6)

def dfs(cnt):
    global ans
    tot=0
    V=0
    for i in range(len(cnt)):
        tot+=cnt[i]*weights[i]
        if cnt[i]>a[i][1]:
            return
        V+=a[i][2][0]-a[i][2][cnt[i]]
    if tot>W:
        return
    ans=max(ans,V)
    for i in range(len(cnt)):
        l=[cnt[j] + (1 if i==j else 0) for j in range(len(cnt))]
        dfs(l)

dfs(cnt0)

print(ans)