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-----
4 6
2 1
3 4
4 10
3 4

-----Sample Output-----
11

The first and third items should be selected.

Difficulty: interview

Starter code:

Solutions:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,w=map(int,input().split())
knap=[[] for i in range(4)]
w0,v=map(int,input().split())
knap[0].append(v)
for i in range(n-1):
    W,v=map(int,input().split())
    knap[W-w0].append(v)
for i in range(4):
    knap[i].sort(reverse=1)
    knap[i]=[0]+knap[i]
for i in range(4):
    for j in range(1,len(knap[i])):
        knap[i][j]+=knap[i][j-1]
ans=0
for a in range(len(knap[0])):
    for b in range(len(knap[1])):
        for c in range(len(knap[2])):
            for d in range(len(knap[3])):
                if w0*a+(w0+1)*b+(w0+2)*c+(w0+3)*d<=w:
                    ans=max(ans,knap[0][a]+knap[1][b]+knap[2][c]+knap[3][d])
print(ans)

n,w = list(map(int,input().split()))
pack_list = [list(map(int,input().split())) for _  in range(n)]

# dp = [[float('inf') for _ in range(10**7+1)] for _ in range(n+1)]
# dp[0] = [0 for _ in range(10**7+1)]

dp_dict = {0: {0:0}} # w,v

'''
for i,pack in enumerate(pack_list):
    for value,weight in enumerate(dp[i]):
        dp[i+1][value] = min(dp[i][value],dp[i+1][value])
        dp[i+1][value+pack[1]] = min(dp[i+1][value+pack[1]],dp[i][value]+pack[0])

for i,num in enumerate(dp[-1][::-1]):
    if num <= w:
        print(10**7-i)'''

for i,pack in enumerate(pack_list):
    i += 1
    if i not in dp_dict:
        dp_dict[i] = {}
    for weight,v in list(dp_dict[i-1].items()):
        if weight not in dp_dict[i]:
            dp_dict[i][weight] = v
        else:
            dp_dict[i][weight] = max(dp_dict[i][weight],v)
        if weight+pack[0] <= w:
            if weight+pack[0] not in dp_dict[i]:
                dp_dict[i][weight+pack[0]] = v+pack[1]
            else:
                dp_dict[i][weight+pack[0]] = max(dp_dict[i][weight+pack[0]],v+pack[1])

target = dp_dict[n]
max_num = 0

for k,v in list(target.items()):
    if k <= w:
        max_num = max(max_num,v)

print(max_num)



n,w=list(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)


N, W = map(int, input().split())
data = tuple(tuple(map(int, input().split())) for _ in range(N))
table = [dict() for _ in range(N + 1)]
table[0][0] = 0
for n in range(N):
    weight, value = data[n]
    for w, now in table[n].items():
        table[n + 1][w] = max(table[n + 1].get(w, 0), now)
        if w + weight <= W:
            table[n + 1][w + weight] = max(table[n + 1].get(w + weight, 0), now + value)
print(max(table[N].values()))

# 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) 

n,w=list(map(int,input().split()))
w_sub,v_sub=list(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=list(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)


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

w1,v1 = map(int,input().split())
stuff = [[] for _ in range(4)]
stuff[0].append(v1)

for _ in range(N-1):
    w,v = map(int,input().split())
    stuff[w-w1].append(v)

for i in stuff:
    i.sort(reverse=True)

ans = 0

for a in range(len(stuff[0])+1):
    for b in range(len(stuff[1])+1):
        for c in range(len(stuff[2])+1):
            for d in range(len(stuff[3])+1):

                if a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3) <= W:
                    ans = max(ans,sum(stuff[0][:a])+sum(stuff[1][:b])+sum(stuff[2][:c])+sum(stuff[3][:d]))

print(ans)

N, W = map(int, input().split())
wv = []
w0 = []
w1 = []
w2 = []
w3 = []
for i in range(N):
    wv.append(list(map(int, input().split())))
wv.sort(key=lambda x:(x[0], -x[1]))

wbase = wv[0][0]
for w, v in wv:
    if(w == wbase):
        w0.append(v)
    elif(w == wbase+1):
        w1.append(v)
    elif(w == wbase+2):
        w2.append(v)
    else:
        w3.append(v)
        
sw0, sw1, sw2, sw3 = [0], [0], [0], [0]
s = 0
for v in w0:
    s += v
    sw0.append(s)
s = 0
for v in w1:
    s += v
    sw1.append(s)
s = 0
for v in w2:
    s += v
    sw2.append(s)
s = 0
for v in w3:
    s += v
    sw3.append(s)
    
value = 0
ans = 0
for i in range(len(sw0)):
    if(wbase*i > W):
        break
    for j in range(len(sw1)):
        if(wbase*i+(wbase+1)*j > W):
            break
        for k in range(len(sw2)):
            if(wbase*i+(wbase+1)*j+(wbase+2)*k > W):
                break
            for l in range(len(sw3)):
                if(wbase*i+(wbase+1)*j+(wbase+2)*k+(wbase+3)*l > W):
                    break
                value = sw0[i]+sw1[j]+sw2[k]+sw3[l]
                ans = max(ans, value)        
print(ans)          

n,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[] for _ in range(4)]
for i,j in a:
    b[i-a[0][0]].append(j)
for i in range(4):
    b[i].sort()
    b[i].reverse()
for i in range(4):
    for j in range(1,len(b[i])):
        b[i][j] += b[i][j-1]
    b[i].reverse()
    b[i].append(0)
    b[i].reverse()
#print(b)
ans = 0
for i in range(len(b[0])):
    for j in range(len(b[1])):
        for k in range(len(b[2])):
            for l in range(len(b[3])):
                #print(i,j,k,l)
                if a[0][0]*i+(a[0][0]+1)*j+(a[0][0]+2)*k+(a[0][0]+3)*l <= w:
                    #print(i,j,k,l)
                    ans = max(ans, b[0][i]+b[1][j]+b[2][k]+b[3][l])
print(ans)

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

memo = {}

def  nap(i, j):
    if i == N:
        return 0

    if (i, j) in memo:
        return memo[i, j]
    elif w_v[i][0] > j:
        temp = nap(i+1, j)
    else:
        temp = max(nap(i+1, j), nap(i+1, j-w_v[i][0]) + w_v[i][1])
    memo[i, j] = temp

    return memo[i, j]

print(nap(0, W))

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

value_table = [[] for i in range(4)]
for i in range(N):
    w, v = map(int,input().split())
    if i == 0:
        w1 = w
    value_table[w-w1] += [v]

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

ans = 0
value_table_ruiseki = [[0] for i in range(4)]
for i in range(4):
    for v in value_table[i]:
        value_table_ruiseki[i] += [value_table_ruiseki[i][-1] + v]

ans = 0
for i, iv in enumerate(value_table_ruiseki[0]):
    for j, jv in enumerate(value_table_ruiseki[1]):
        for k, kv in enumerate(value_table_ruiseki[2]):
            for ell, ellv in enumerate(value_table_ruiseki[3]):
                weight = i*w1 + j*(w1+1) + k*(w1+2) + ell*(w1+3)
                value = iv + jv + kv + ellv
                if weight <=W:
                    ans = max(ans, value)

print(ans)

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

W1,V1 = map(int, input().split())

P = {W1:[V1], W1+1:[], W1+2:[], W1+3:[]}

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

PS={}
for k,v in P.items():
  v.sort(reverse=True)
  S = [0] * (len(v)+1)
  for i in range(len(v)):
    S[i+1] = S[i] + v[i]
  PS[k] = S
  
#print(P)
#print(PS)
A,B,C,D = len(PS[W1]), len(PS[W1+1]), len(PS[W1+2]), len(PS[W1+3])
ans = 0
for a in range(A):
  for b in range(B):
    for c in range(C):
      for d in range(D):
        if a*W1 + b*(W1+1) + c*(W1+2) + d*(W1+3) > W:
          continue
        ans = max(ans, PS[W1][a] + PS[W1+1][b] + PS[W1+2][c] + PS[W1+3][d])
        
print(ans)

import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = list(map(int, read().split()))
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            ans = max(ans, rec(i + 1, w + (w_min + i) * j, v + csums[i][j]))

        return ans

    print((rec(0, 0, 0)))
    return


def __starting_point():
    main()

__starting_point()

from collections import defaultdict
n, W = list(map(int, input().split()))
dd = defaultdict(list)
for i in range(n):
    weight, value = list(map(int, input().split()))
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            if W < a*w+b*x+c*y:
                break
            z = min((W-a*w-b*x-c*y)//d, len(dd[d]))
            val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
            ans = max(ans, val)
print(ans)


import numpy as np
from itertools import product
from collections import  defaultdict as dd
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
wi = wv[0][0]
vi = wv[0][1]
dic = dd(list)
dic_cumsum = dd(list)
for w,v in wv:
    dic[w].append(v)

for k,v in list(dic.items()):
    tmp = sorted(v, reverse=True)
    dic_cumsum[k] = [0] + list(np.zeros((N + 1), dtype=np.int64))
    dic_cumsum[k][1:] = list(np.cumsum(tmp, dtype=np.int64))
for i in range(1,4):
    if wi+i not in list(dic_cumsum.keys()):
        dic_cumsum[wi+i] = [0]
        
n = [len(dic_cumsum[wi]), len(dic_cumsum[wi+1]), len(dic_cumsum[wi+2]), len(dic_cumsum[wi+3])]
m = [list(range(val)) for val in n]
res = 0

for ls in product(m[0], m[1], m[2]):
    if sum(ls)*wi > W:
        continue
    tmp_value = 0
    tmp_weight = 0
    for i,k in enumerate(ls):
        tmp_value += dic_cumsum[wi + i][k]
        tmp_weight += k*(wi+i)
    if tmp_weight > W:
        continue
    # wi, wi+1, wi+2の個数が決まっているので、wi+3を何個取れるかはO(1)で求められる
    max_m3 = (W - tmp_weight) // (wi+3)
    m3 = min(max_m3, n[3]-1)
    tmp_value += dic_cumsum[wi+3][m3]
    if tmp_value > res:
        res = tmp_value
print(res)




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)

N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
mw = wv[0][0]
wv.sort(key=lambda x: -x[1])
values = [[] for _ in range(4)]
for w, v in wv:
    values[w-mw].append(v)


def solve(n, w, c):
    if n >= 4 or w >= W or c >= N:
        return 0
    r = 0
    for i in range(len(values[n])+1):
        cw = w + (mw + n) * i
        cc = c + i
        if cw <= W and cc <= N:
            r = max(r, sum(values[n][0:i]) + solve(n+1, cw, cc))
    return r


print((solve(0, 0, 0)))


n,W=list(map(int,input().split()))
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][min(W-i*w0,400)])
print(ans)



from collections import *
N,W = map(int,input().split())
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w1,v1 = map(int,input().split())
  for w2,v2 in dp.copy().items():
    if w1+w2<=W:
      dp[w1+w2] = max(dp[w1+w2],v1+v2)

print(max(dp.values()))

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 list(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)


n,w=list(map(int,input().split()))
w_sub,v_sub=list(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=list(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)


N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Bag = dd(lambda:0)
Bag[0] = 0
for w,v in Items:
    temp = [(key+w,Bag[key]+v) for key in Bag if key + w <= W]
    for key,value in temp:
        Bag[key] = max(Bag[key],value)
ans = max(Bag.values())
print(ans)

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print(('\n'.join(x)))
def printni(x): print(('\n'.join(list(map(str,x)))))
inf = 10**17
mod = 10**9 + 7

n,w=MI()
lis=[LI() for i in range(n)]
u=lis[0][0]
vals=[[] for i in range(4)]
for i in range(n):
    if lis[i][0]==u:
        vals[0].append(lis[i][1])
    elif lis[i][0]==u+1:
        vals[1].append(lis[i][1])
    elif lis[i][0]==u+2:
        vals[2].append(lis[i][1])
    else:
        vals[3].append(lis[i][1])
#print(vals)
for i in range(4):
    vals[i].sort(reverse=True)
    vals[i]=list(accumulate(vals[i]))
    vals[i]=[0]+vals[i]
mx=0
#print(vals)
for i in range(len(vals[0])):
    for j in range(len(vals[1])):
        for k in range(len(vals[2])):
            for l in range(len(vals[3])):
                if u*i+(u+1)*j+(u+2)*k+(u+3)*l>w:
                    continue
                V=vals[0][i]+vals[1][j]+vals[2][k]+vals[3][l]
                if V>mx:
                    mx=V
print(mx)
            
        

    

        
        
        
            
        

                


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

dp = [[[0]*(3*n+1) for _ in range(n)] for _ in range(n)]

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*(j+1)+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

import sys
from collections import defaultdict

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    weight = set()
    weight.add(0)
    weight.add(WV[0][0])
    for i in range(1, N + 1):
        for j in range(3 * i):
            weight.add(WV[0][0] * i + j)

    weight = sorted(list(weight))

    dp = defaultdict(int)

    for i in range(N):
        for j in weight[::-1]:
            if j >= WV[i][0]:
                dp[j] = max(dp[j], dp[j - WV[i][0]] + WV[i][1])

    ans = 0
    for i in weight:
        if i > W:
            break
        ans = max(ans, dp[i])

    print(ans)


def __starting_point():
    main()

__starting_point()

from sys import stdin
import numpy as np

def main():
    def itrsum(arr):
        n=len(arr)
        tri=np.array([[i>=j for i in range(n)] for j in range(n+1)])
        return np.dot(tri,arr).astype('int64')
    n,w=list(map(int,stdin.readline().strip().split()))
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    # arr=[sorted([x for x in t if x[0]==w1+i],reverse=True,key=lambda e:e[1]) for i in range(4)]
    arr=[[x for x in t if x[0]==w1+i] for i in range(4)]
    arr=[l for l in arr]
    lenarr=list(map(len,arr))
    arr0=[itrsum(np.array(sorted([x[0] for x in l]),dtype='int64')) for l in arr]
    arr1=[itrsum(np.array(sorted([x[1] for x in l]),dtype='int64')) for l in arr]
    # arr=[x.sort(reverse=True,key=lambda e:e[1]) for x in arr]
    arr=np.array(arr)
    arrw=0
    arrv=0
    for i in range(4):
        arrw=np.ravel(arr0[i].reshape(lenarr[i]+1,1)+np.array([arrw]))
        arrv=np.ravel(arr1[i].reshape(lenarr[i]+1,1)+np.array([arrv]))
    #print(arr0)
    #print(arr1)
    #print('\n')
    #print(arrw)
    #print(arrv)
    #print(arrv[arrw<=w])
    ansarr=arrv[arrw<=w]
    print((np.max(ansarr)))
    # wts=list(map(lambda l:l[0]-w1-1, t))
    # val=list(map(lambda l:l[1], t))

def __starting_point():
    main()   

__starting_point()

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)

def __starting_point():
    main()
__starting_point()

from collections import defaultdict
N,W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
DP = defaultdict(int)
DP[0] = 0
for weight, value in wv:
  exists = list(DP.items())
  for key, total in exists:
    new_key = key + weight
    if new_key > W:
      continue
    new_total = total + value
    if DP[new_key] < new_total:
      DP[new_key] = new_total

print(max(DP.values()))

from collections import defaultdict


def main():
    n, w = list(map(int, input().split()))
    items = [list(map(int, input().split())) for _ in range(n)]
    DP = defaultdict(int)
    DP[0] = 0
    for weight, value in items:
        exists = list(DP.items())
        for key, total in exists:
            new_key = key + weight
            if new_key > w:
                continue
            new_total = total + value
            if DP[new_key] < new_total:
                DP[new_key] = new_total

    print((max(DP.values())))


def __starting_point():
    main()

__starting_point()

def main():
    n, w = list(map(int, input().split()))
    w1, v1 = list(map(int, input().split()))
    values = [[] for _ in range(4)]
    values[0].append(v1)
    for _ in range(n - 1):
        wi, vi = list(map(int, input().split()))
        values[wi - w1].append(vi)
    for i in range(4):
        values[i].sort(reverse=True)
    prefix = [[0] for _ in range(4)]
    for i in range(4):
        for j in range(len(values[i])):
            prefix[i].append(prefix[i][-1] + values[i][j])
    max_ans = 0
    tot_val = [0] * 4
    tot_weights = [0] * 4
    for i in range(min(len(values[0]), w // w1) + 1):
        tot_val[0] = prefix[0][i]
        tot_weights[0] = w1 * i
        for j in range(min(len(values[1]), w // (w1 + 1)) + 1):
            tot_val[1] = tot_val[0] + prefix[1][j]
            tot_weights[1] = tot_weights[0] + (w1 + 1) * j
            if tot_weights[1] > w:
                break
            for k in range(min(len(values[2]), w // (w1 + 2)) + 1):
                tot_val[2] = tot_val[1] + prefix[2][k]
                tot_weights[2] = tot_weights[1] + k * (w1 + 2)
                if tot_weights[2] > w:
                    break
                diff = w - tot_weights[2]
                min_select = min(diff // (w1 + 3), len(values[3]))
                tot_val[3] = tot_val[2] + prefix[3][min_select]
                tot_weights[3] = tot_weights[2] + min_select * (w1 + 3)
                max_ans = max(max_ans, tot_val[3])
    print(max_ans)


def __starting_point():
    main()

__starting_point()

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

dp = [[[0]*(3*n+1) for _ in range(n)] for _ in range(n)]

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*n+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

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())
ws=w[0]
V=[[] for i in range(4)]
for i in range(n):
  V[w[i]-ws].append(v[i])
V[0].sort(reverse=True)
V[1].sort(reverse=True)
V[2].sort(reverse=True)
V[3].sort(reverse=True)
VV=[[0] for i in range(4)]
for i in range(4):
  for j in range(len(V[i])):
    VV[i].append(VV[i][-1]+V[i][j])
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):
        if i*ws+j*(ws+1)+k*(ws+2)+l*(ws+3)>W:
          break
        if VV[0][i]+VV[1][j]+VV[2][k]+VV[3][l]>ans:
          ans=VV[0][i]+VV[1][j]+VV[2][k]+VV[3][l]
print(ans)

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

w_to_idx = {0:0}
idx_to_w = {0:0}
idx_W = 0
def calc():
  nonlocal w_to_idx, idx_to_w, idx_W
  idx = 1
  w_max = 0
  for i in range(1, N+1):
    w = w1*i
    for j in range(3*i + 1):
      ww = w + j
      if ww in w_to_idx:
        continue
      w_to_idx[ww] = idx
      idx_to_w[idx] = ww
      if w_max < ww <= W:
        w_max = ww
        idx_W = idx
      idx += 1

calc()
n = len(w_to_idx)
dp = [[0]*n for i in range(N+1)]
for i, (w, v) in enumerate(wv, 1):
  for j in range(n):
    dp[i][j] = dp[i-1][j]
    ww = idx_to_w[j]
    if ww >= w and ww-w in w_to_idx:
      jj = w_to_idx[ww - w]
      dp[i][j] = max(dp[i][j], dp[i-1][jj] + v)

print(max(dp[-1][:idx_W+1]))

# coding: utf-8
# Your code here!
def saiki(value,HP,num):
    if num==0:
        #print(HP//base)
        value+=wa[0][min(HP//base,len(wa[0])-1)]
        ans.append(value)
    else:
        for i in range(len(wa[num])):
            if HP-(num+base)*i>=0:
                saiki(value+wa[num][i],HP-(num+base)*i,num-1)
            else:
                break
    return


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

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

for i in range(N):
    w,v=list(map(int,input().split()))
    if i==0:
        base=w
    lis[w-base].append(v)

lis=list([sorted(x, reverse=True) for x in lis])

wa=[[0] for i in range(4)]

for i in range(len(wa)):
    for item in lis[i]:
        wa[i].append(wa[i][-1]+item)

#print(wa)

ans=[]
saiki(0,W,3)
    

print((max(ans)))


from collections import *
N,W = map(int,input().split())
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w,v = map(int,input().split())
  for k,b in dp.copy().items():
    if k+w<=W:
      dp[k+w] = max(dp[k+w],b+v)

print(max(dp.values()))

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)

V = [[], [], [], []]
for wi, vi in zip(w, v):
  V[wi - w[0]].append(vi)

for vv in V:
  vv.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):
        if w[0] * i + (w[0] + 1)* j + (w[0]+2)*k + (w[0] + 3) * l <= W:
          ans = max(ans, sum(V[0][:i]) +sum(V[1][:j]) +sum(V[2][:k]) +sum(V[3][:l])) 
print(ans)

n, w_max = list(map(int, input().split()))
W, V = [], []
Diff_zero = []
Diff_one = []
Diff_two = []
Diff_three = []
for i in range(n):
    w, v = list(map(int, input().split()))
    W.append(w)
    V.append(v)
    diff = w - W[0]
    if diff == 0:
        Diff_zero.append(v)
    elif diff == 1:
        Diff_one.append(v)
    elif diff == 2:
        Diff_two.append(v)
    elif diff == 3:
        Diff_three.append(v)

Diff_zero = sorted(Diff_zero, reverse=True)
Diff_one = sorted(Diff_one, reverse=True)
Diff_two = sorted(Diff_two, reverse=True)
Diff_three = sorted(Diff_three, reverse=True)

Diff_zero_ruiseki = [0]
Diff_one_ruiseki = [0]
Diff_two_ruiseki = [0]
Diff_three_ruiseki = [0]

for i in range(len(Diff_zero)):
    Diff_zero_ruiseki.append(Diff_zero[i] + Diff_zero_ruiseki[-1])
for i in range(len(Diff_one)):
    Diff_one_ruiseki.append(Diff_one[i] + Diff_one_ruiseki[-1])
for i in range(len(Diff_two)):
    Diff_two_ruiseki.append(Diff_two[i] + Diff_two_ruiseki[-1])
for i in range(len(Diff_three)):
    Diff_three_ruiseki.append(Diff_three[i] + Diff_three_ruiseki[-1])

value_max = 0
w_zero = W[0]

for i in range(n+1):
    if i > len(Diff_zero):
        continue
    for j in range(n+1):
        if j > len(Diff_one):
            continue
        for k in range(n+1):
            if k > len(Diff_two):
                continue
            for l in range(n+1):
                if l > len(Diff_three):
                    continue
                if w_zero*i + (w_zero+1)*j + (w_zero+2)*k + (w_zero+3)*l > w_max:
                    continue
                if i + j + k + l > n:
                    continue

                value = Diff_zero_ruiseki[i] + Diff_one_ruiseki[j] + Diff_two_ruiseki[k] + Diff_three_ruiseki[l]
                value_max = max(value, value_max)

print(value_max)


             


import numpy as np
N, W = list(map(int,input().split()))
ls = []
for i in range(N):
  w, v = list(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)))


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 list(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(list(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)






from itertools import accumulate
N,W=map(int,input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)
for _ in range(N-1):
    a, b = map(int, input().split())
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)


for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)

w1=[0]+w1
w1=list(accumulate(w1))
w2=[0]+w2
w2=list(accumulate(w2))
w3=[0]+w3
w3=list(accumulate(w3))
w4=[0]+w4
w4=list(accumulate(w4))

#print(w1,w2,w3,w4)
#print(len(w1),len(w2),len(w3),len(w4))

ans=0
for a in range(len(w1)):
    for b in range(len(w2)):
        for c in range(len(w3)):
            for d in range(len(w4)):
                #print(a,b,c,d)
                wei=w*a+(w+1)*b+(w+2)*c+(w+3)*d
                val=w1[a]+w2[b]+w3[c]+w4[d]
                #print(wei,val)
                if wei<=W:
                    ans=max(val,ans)

print(ans)

n, W = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]

base = a[0][0]
s = [[] for _ in range(4)]
for w, v in a:
    s[w-base].append(v)
for i in range(4):
    s[i].sort(reverse=True)

length = [len(s[i]) for i in range(4)]
cum = [[] for _ in range(4)]
for i in range(4):
    cum[i] = [0 for _ in range(length[i]+1)]
    for j in range(length[i]):
        cum[i][j+1] = cum[i][j] + s[i][j]

ans = 0
for i in range(length[0]+1):
    for j in range(length[1]+1):
        for k in range(length[2]+1):
            for l in range(length[3]+1):
                weight = (i+j+k+l) * base + j + 2*k + 3*l
                if weight <= W:
                    ans = max(ans, cum[0][i] + cum[1][j] + cum[2][k] + cum[3][l])
print(ans)

N, W = list(map(int,input().split()))
ls = []
for i in range(N):
  w, v = list(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)


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,W = list(map(int,readline().split()))
goods = [tuple(map(int,readline().split())) for i in range(N)]

from collections import defaultdict

d = defaultdict(int)
d[0] = 0

for (w,v) in goods:
    dnew = defaultdict(int)
    for key,value in list(d.items()):
        dnew[key] = value
    for key,value in list(d.items()):
        dnew[key+w] = max(dnew[key+w],d[key]+v)
    d = dnew
ans = 0
for k,v in list(d.items()):
    if k <= W:
        ans = max(ans,v)
print(ans)



n,W=map(int,input().split())
wv=[[]for _ in range(4)]
for i in range(n):
	w,v=map(int,input().split())
	if i==0:
		r=w
		wv[0].append(v)
	else:
		wv[w-r].append(v)
for i in range(4):
	wv[i].sort(reverse=True)
	for j in range(len(wv[i])-1):
		wv[i][j+1]+=wv[i][j]
	wv[i].insert(0,0)
ans=0
for i in range(len(wv[0])):
	for j in range(len(wv[1])):
		for k in range(len(wv[2])):
			for l in range(len(wv[3])):
				p=wv[0][i]+wv[1][j]+wv[2][k]+wv[3][l]
				if i*r+j*(r+1)+k*(r+2)+l*(r+3)<=W:
					ans=max(ans,p)
print(ans)

# solution
import io

nim, mike = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(nim)]
qwe = {}
qwe[0] = 0
for weight, value in WV:
    dp_old = qwe.copy()
    for k, v in list(dp_old.items()):
        if k + weight <= mike:
            qwe[k + weight] = max(qwe.get(k + weight, 0), v + value)
ans = 0
for k, v in list(qwe.items()):
    ans = max(ans, v)
print(ans)


N,W=map(int,input().split())
A=[]
W1,W2,W3,W4=[],[],[],[]
for i in range(N):
  w,v=map(int,input().split())
  if i==0:
    a=w
  A.append((v,w))
  if w-a==0:
    W1.append(v)
  elif w-a==1:
    W2.append(v)
  elif w-a==2:
    W3.append(v)
  else:
    W4.append(v)
  

W1,W2,W3,W4=sorted(W1)[::-1],sorted(W2)[::-1],sorted(W3)[::-1],sorted(W4)[::-1]

l1,l2,l3,l4=len(W1),len(W2),len(W3),len(W4)
ans=0
for i in range(l1+1):
  for j in range(l2+1):
    for k in range(l3+1):
      for l in range(l4+1):
        value=sum(W1[:i])+sum(W2[:j])+sum(W3[:k])+sum(W4[:l])
        if a*i+(a+1)*j+(a+2)*k+(a+3)*l<=W:
          ans=max(ans,value)
print(ans)

import sys
from operator import itemgetter

rl = sys.stdin.readline


def solve():
    N, W = list(map(int, rl().split()))
    w1, w2, w3, w4 = [[0, 0]], [[0, 0]], [[0, 0]], [[0, 0]]
    w1.append(list(map(int, rl().split())))
    min_w = w1[1][0]
    for _ in range(N - 1):
        w, v = list(map(int, rl().split()))
        d = w - min_w
        if d == 0:
            w1.append([w, v])
        elif d == 1:
            w2.append([w, v])
        elif d == 2:
            w3.append([w, v])
        else:
            w4.append([w, v])
    w1.sort(key=itemgetter(1), reverse=True)
    w2.sort(key=itemgetter(1), reverse=True)
    w3.sort(key=itemgetter(1), reverse=True)
    w4.sort(key=itemgetter(1), reverse=True)
    
    ans = 0
    for i in range(len(w1)):
        w_tmp1, v_tmp1 = 0, 0
        for j in range(i):
            w_tmp1 += w1[j][0]
            v_tmp1 += w1[j][1]
        for j in range(len(w2)):
            w_tmp2, v_tmp2 = w_tmp1, v_tmp1
            for k in range(j):
                w_tmp2 += w2[k][0]
                v_tmp2 += w2[k][1]
            for k in range(len(w3)):
                w_tmp3, v_tmp3 = w_tmp2, v_tmp2
                for l in range(k):
                    w_tmp3 += w3[l][0]
                    v_tmp3 += w3[l][1]
                for l in range(len(w4)):
                    w_tmp4, v_tmp4 = w_tmp3, v_tmp3
                    for m in range(l):
                        w_tmp4 += w4[m][0]
                        v_tmp4 += w4[m][1]
                    if w_tmp4 <= W:
                        ans = max(ans, v_tmp4)
    print(ans)


def __starting_point():
    solve()

__starting_point()

n, w = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
ss = s[0][0]
s.sort(key = lambda x : x[1], reverse = True)
t = [[] for _ in range(4)]
for u in s:
    t[u[0] - ss].append(u[1])
l1, l2, l3, l4 = len(t[0]) + 1, len(t[1]) + 1, len(t[2]) + 1, len(t[3]) + 1
a, b, = [0] * l1, [0] * l2
c, d, = [0] * l3, [0] * l4
for i in range(1, l1):
    a[i] = t[0][i - 1] + a[i - 1]
for i in range(1, l2):
    b[i] = t[1][i - 1] + b[i - 1]
for i in range(1, l3):
    c[i] = t[2][i - 1] + c[i - 1]
for i in range(1, l4):
    d[i] = t[3][i - 1] + d[i - 1]
ans = 0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for l in range(l4):
                if ss * (i + j + k + l) + (j + 2 * k + 3 * l) <= w:
                    ans = max(ans, a[i] + b[j] + c[k] + d[l])
print(ans)

from sys import stdin
from itertools import accumulate
readline = stdin.readline

N, W = list(map(int, input().split()))
vs = [[] for _ in range(4)]
w, v = list(map(int, input().split()))
w1 = w
vs[0].append(v)
for _ in range(N - 1):
    w, v = list(map(int, input().split()))
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = [0] + list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0])):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1])):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2])):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = vs[0][i] + vs[1][j] + vs[2][k]
            for l in range(len(vs[3])):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                result = max(result, t + vs[3][l])
print(result)


n,w=list(map(int,input().split()))
w_sub,v_sub=list(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=list(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)


from collections import defaultdict
n, W = list(map(int, input().split()))
dd = defaultdict(list)
for i in range(n):
    weight, value = list(map(int, input().split()))
    dd[weight].append(value)

for k in list(dd.keys()):
    dd[k].sort(reverse=True)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = sum(dd[a][:w])+sum(dd[b][:x]) + \
                    sum(dd[c][:y])+sum(dd[d][:z])
                ans = max(ans, val)
print(ans)


from collections import defaultdict
n, W = list(map(int, input().split()))
dd = defaultdict(list)
for i in range(n):
    weight, value = list(map(int, input().split()))
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
                ans = max(ans, val)
print(ans)


N, W = list(map(int, input().split()))
item = [tuple(map(int, input().split())) for _ in range(N)]

w1 = item[0][0]
V = [[] for _ in range(4)]
for w, v in item:
    V[w - w1].append(v)
for i in range(4):
    V[i].sort(reverse=True)

cnt = [0] * 4
for i in range(4):
    cnt[i] = len(V[i])

ans = 0
for i in range(cnt[0] + 1):
    S0 = sum(V[0][:i])
    W0 = i * w1
    for j in range(cnt[1] + 1):
        S1 = sum(V[1][:j])
        W1 = j * (w1 + 1)
        for k in range(cnt[2] + 1):
            S2 = sum(V[2][:k])
            W2 = k * (w1 + 2)
            for l in range(cnt[3] + 1):
                S3 = sum(V[3][:l])
                W3 = l * (w1 + 3)
                if W0 + W1 + W2 + W3 <= W:
                    ans = max(ans, S0 + S1 + S2 + S3)

print(ans)


n,w=list(map(int,input().split()))
w_sub,v_sub=list(map(int,input().split()))
w0=w_sub
x_sub=[[v_sub],[],[],[]]
for i in range(n-1):
    w_sub,v_sub=list(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)


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)

n,w=list(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)


from itertools import product

N, W = map(int,input().split())
L = [[] for _ in range(4)]
w, v = map(int,input().split())
L[0].append(v)
for _ in range(N-1):
    tmp_w, tmp_v = map(int,input().split())
    L[tmp_w - w].append(tmp_v)

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

for i in range(4):
    for j in range(len(L[i]) - 1):
        L[i][j+1] += L[i][j]
    L[i] = [0] + L[i]

ans = 0

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

print(ans)

N, W = list(map(int, input().split()))
wv = list(map(int, input().split()))
w1 = wv[0]

wvs = [[] for i in range(4)]
wvs[0].append(wv[1])

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

s = [0] * 4
for i in range(4):
  wvs[i] = sorted(wvs[i], reverse = True)
  s[i] = len(wvs[i])
  if s[i] > 1:
    for j in range(1, s[i]):
      wvs[i][j] += wvs[i][j - 1]
  wvs[i].insert(0, 0)
#print(wvs)

ans = 0
for i in range(s[0] + 1):
  for j in range(s[1] + 1):
    for k in range(s[2] + 1):
      for l in range(s[3] + 1):
        weight = w1 * (i + j + k + l) + (j + 2 * k + 3 * l)
        if weight <= W:
          value = wvs[0][i] + wvs[1][j] + wvs[2][k] + wvs[3][l]
          ans = max(ans, value)
          
print(ans)
        
        


  
  


N, W = map(int, input().split())
data = tuple(tuple(map(int, input().split())) for _ in range(N))
d = {0: 0}
for n in range(N):
    weight, value = data[n]
    for w, now in d.copy().items():
        if w + weight <= W:
            d[w + weight] = max(d.get(w + weight, 0), now + value)
print(max(d.values()))

#060_D
n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)
for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)
    
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)

N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Bag = dd(lambda:0)
Bag[0] = 0
for w,v in Items:
    temp = [(key+w,Bag[key]+v) for key in Bag if key + w <= W]
    for key,value in temp:
        Bag[key] = max(Bag[key],value)
ans = max(Bag.values())
print(ans)

n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
num = wv[0][0]
dp = [[-float("inf") for i in range(3 * (n - 1) + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    w, v = wv[i][0], wv[i][1]
    w -= num
    for j in range(n - 1, -1, -1):
        for k in range(3 * (n - 1) + 1 - w):
            dp[j + 1][k + w] = max(dp[j + 1][k + w], dp[j][k] + v)
ans = 0
for i in range(3 * (n - 1) + 1):
    for j in range(n + 1):
        if j * num + i <= W:
            ans = max(ans, dp[j][i])
print(ans)

from collections import defaultdict


def main():
    n, w = list(map(int, input().split()))
    items = [list(map(int, input().split())) for _ in range(n)]
    DP = defaultdict(int)
    DP[0] = 0
    for weight, value in items:
        exists = list(DP.items())
        for key, total in exists:
            new_key = key + weight
            new_total = total + value
            if DP[new_key] < new_total:
                DP[new_key] = new_total

    candidates = [0]
    for weight, value in sorted(DP.items()):
        if weight > w:
            break
        candidates.append(value)

    print((max(candidates)))


def __starting_point():
    main()

__starting_point()

import  numpy as np
N, W, *L = map(int, open(0).read().split())
M = 3*(N-1)+1
dp = np.zeros((M,N+1),np.int64)
for w,v in zip(*[iter(L)]*2):
  w -= L[0]
  dp[w:,1:] = np.maximum(dp[w:,1:], dp[:M-w,:N]+v)

ans = 0
for i in range(N+1):
  m = i*L[0]
  if m>W:
    continue
  m = min(W-m,M-1)
  ans = max(ans, dp[m,i])
print(ans)

n,w=list(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)


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)

import itertools
from collections import defaultdict

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

for i in d:
    d[i] = list(itertools.accumulate(sorted(d[i], reverse=True)))
mm = min(d)

ans = 0
for t in itertools.product(list(range(len(d[mm]) + 1)), list(range(len(d[mm + 1]) + 1)),
                           list(range(len(d[mm + 2]) + 1)), list(range(len(d[mm + 3]) + 1))):
    if sum((mm + i) * t[i] for i in range(4)) > W:
        continue
    ans = max(ans, sum(d[mm + i][t[i] - 1] if t[i] else 0 for i in range(4)))
print(ans)


from collections import defaultdict


def main():
    N, W = list(map(int, input().split(' ')))
    items, cumsums = defaultdict(list), defaultdict(list)
    w_0 = 0
    for i in range(N):
        w, v = list(map(int, input().split(' ')))
        if i == 0:
            w_0 = w
        items[w].append(v)
    for w in items.keys():
        items[w].sort(reverse=True)
        cumsum_w, cumsum_v = 0, 0
        for v in items[w]:
            cumsum_w += w
            cumsum_v += v
            # w - w_0 is in [0, 1, 2, 3]
            cumsums[w - w_0].append((cumsum_w, cumsum_v))

    def dfs(cur, rest_w):
        if cur == 0:
            max_v = 0
            for cumsum_w, cumsum_v in cumsums[cur]:
                if cumsum_w <= rest_w:
                    max_v = cumsum_v
            return max_v
        else:
            ret = dfs(cur - 1, rest_w)
            for cumsum_w, cumsum_v in cumsums[cur]:
                if rest_w >= cumsum_w:
                    ret = max([ret, cumsum_v + dfs(cur - 1, rest_w - cumsum_w)])
            return ret

    print(dfs(3, W))


def __starting_point():
    main()
__starting_point()

from itertools import accumulate

N, W = map(int, input().split())
wv = {}
w1 = 0
for i in range(N):
  w, v = map(int, input().split())
  if i == 0:
    w1 = w
  if w in wv:
    wv[w].append(v)
  else:
    wv[w] = [v]

for w in wv:
  wv[w].sort(reverse=True)
  wv[w] = [0] + list(accumulate(wv[w]))

w2 = w1+1; w3 = w1+2; w4 = w1+3
for w in [w1, w1+1, w1+2, w1+3]:
  if w not in wv:
    wv[w] = [0]

ans = 0
for n1 in range(len(wv[w1])):
  for n2 in range(len(wv[w2])):
    for n3 in range(len(wv[w3])):
      for n4 in range(len(wv[w4])):
        w = w1*n1 + w2*n2 + w3*n3 + w4*n4
        if w <= W:
          ans = max(ans, wv[w1][n1]+wv[w2][n2]+wv[w3][n3]+wv[w4][n4])

print(ans)

N, W, *WV = map(int, open(0).read().split())

C = {0: 0}
for v, w in zip(*[reversed(WV)] * 2):
    for x, y in C.copy().items():
        if x + w <= W:
            C[x + w] = max(C.get(x + w, 0), y + v)

print(max(C.values()))

from sys import stdin
from itertools import accumulate
readline = stdin.readline

N, W = list(map(int, input().split()))
vs = [[] for _ in range(4)]
w, v = list(map(int, input().split()))
w1 = w
vs[0].append(v)
for _ in range(N - 1):
    w, v = list(map(int, input().split()))
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0]) + 1):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1]) + 1):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2]) + 1):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = 0
            if i != 0:
              t += vs[0][i - 1]
            if j != 0:
              t += vs[1][j - 1]
            if k != 0:
              t += vs[2][k - 1]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                if l == 0:
                    result = max(result, t)
                else:
                    result = max(result, t + vs[3][l -1])
print(result)


n,w=list(map(int,input().split()))
x1,y1=list(map(int,input().split()))
d={x1:[y1],x1+1:[],x1+2:[],x1+3:[]}
for _ in range(n-1):
    x,y=list(map(int,input().split()))
    d[x].append(y)
d={k:[0]+sorted(d[k],reverse=True) for k in d}
vm=0
v1,w1=0,0
for e in d[x1]:
    v1+=e
    w1+=0 if e==0 else x1
    v2,w2=0,0
    for f in d[x1+1]:
        v2+=f
        w2+=0 if f==0 else x1+1
        v3,w3=0,0
        for g in d[x1+2]:
            v3+=g
            w3+=0 if g==0 else x1+2
            v4,w4=0,0
            for h in d[x1+3]:
                v4+=h
                w4+=0 if h==0 else x1+3
                ws=w1+w2+w3+w4
                vs=v1+v2+v3+v4
                if ws<=w:
                    vm=max(vm,vs)
print(vm)


from operator import itemgetter
n,w=list(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)


n,w=list(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)


n,w=list(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)


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

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = min(W - w1 * j, 3 * n)
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)


from collections import defaultdict
N,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(N)]
dp=defaultdict(int)
dp[0]=0
for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w<=W:
      dp[tw+w]=max(tv+v,dp[tw+w])
print(max(dp.values()))

import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = list(map(int, read().split()))
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            w_next = w + (w_min + i) * j
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))

        return ans

    print((rec(0, 0, 0)))
    return


def __starting_point():
    main()

__starting_point()

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
w0 = wv[0][0]
wv.sort(key=lambda x: (x[0], -x[1]))
w1, w2, w3, w4 = [], [], [], []
for w, v in wv:
    if w == w0:
        w1.append(v)
    elif w == w0 + 1:
        w2.append(v)
    elif w == w0 + 2:
        w3.append(v)
    else:
        w4.append(v)
Sw1, Sw2, Sw3, Sw4 = [0], [0], [0], [0]
S = 0
for v in w1:
    S += v
    Sw1.append(S)
S = 0
for v in w2:
    S += v
    Sw2.append(S)
S = 0
for v in w3:
    S += v
    Sw3.append(S)
S = 0
for v in w4:
    S += v
    Sw4.append(S)
l1, l2, l3, l4 = len(w1), len(w2), len(w3), len(w4)
V = 0
v = 0
for i in range(l1 + 1):
    if w0 * i > W:
        break
    for j in range(l2 + 1):
        if w0 * i + (w0 + 1) * j > W:
            break
        for k in range(l3 + 1):
            if w0 * i + (w0 + 1) * j + (w0 + 2) * k > W:
                break
            for l in range(l4 + 1):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l > W:
                    break
                v = Sw1[i] + Sw2[j] + Sw3[k] + Sw4[l]
                V = max(V, v)
print(V)

from itertools import accumulate

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

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

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

acc = [[0] + list(accumulate(li)) for li in weights]

l3 = len(weights[3])
ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            w_sm = w1 * i + (w1 + 1) * j + (w1 + 2) * k
            if w_sm > W:
                break

            l = min((W - w_sm) // (w1 + 3), l3)
            val = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
            ans = max(ans, val)

print(ans)


n,w=list(map(int,input().split()))
w_sub,v_sub=list(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=list(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)


from collections import defaultdict

N, W = list(map(int, input().split()))
wv = defaultdict(list)
for _ in range(N):
    w, v = list(map(int, input().split()))
    wv[w].append(v)

for k in list(wv.keys()):
    wv[k].sort(reverse=True)

kw = list(wv.keys())
kw.sort()
l = [len(wv[k]) for k in kw]
l = l + (4 - len(l)) * [0]
# print(l)

ans = 0
for i in range(l[0] + 1):
    wi = kw[0] * i
    if W < wi:
        break
    vi = sum(wv[kw[0]][:i])
    if l[1] == 0:
        ans = max(ans, vi)
    for j in range(l[1] + 1):
        if 2 <= len(kw):
            wj = wi + kw[1] * j
            if W < wj:
                break
            vj = vi + sum(wv[kw[1]][:j])
            if l[2] == 0:
                ans = max(ans, vj)
            for k in range(l[2] + 1):
                if 3 <= len(kw):
                    wk = wj + kw[2] * k
                    if W < wk:
                        break
                    vk = vj + sum(wv[kw[2]][:k])
                    if l[3] == 0:
                        ans = max(ans, vk)
                    for m in range(l[3] + 1):
                        if 4 <= len(kw):
                            wm = wk + kw[3] * m
                            if W < wm:
                                break
                            vm = vk + sum(wv[kw[3]][:m])
                            ans = max(ans, vm)
print(ans)


n,w=list(map(int,input().split()))
w_sub,v_sub=list(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=list(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)


import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = list(map(int, read().split()))
    weight = WV[::2]
    value = WV[1::2]

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

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

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, vec):
        if i == 4:
            ans = 0
            w_total = 0
            for j in range(4):
                w_total += (w_min + j) * vec[j]
            if w_total > W:
                return -1
            for j in range(4):
                ans += csums[j][vec[j]]
            return ans
        ans = 0
        for j in range(len(csums[i])):
            vec.append(j)
            ans = max(ans, rec(i + 1, vec))
            vec.pop()
        return ans

    print((rec(0, [])))
    return


def __starting_point():
    main()

__starting_point()

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()


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,W = map(int, input().split())
    w,v = [], []
    for i in range(n):
        a,b = map(int, input().split())
        if i == 0:
            w.append(a)
        else:
            w.append(a - w[0])
        v.append(b)
    #w1の重さ
    base = w[0]
    w[0] = 0
    w0, w1, w2, w3 = [], [], [], []
    for i in range(n):
        if w[i] == 0:
            w0.append(v[i])
        if w[i] == 1:
            w1.append(v[i])
        if w[i] == 2:
            w2.append(v[i])
        if w[i] == 3:
            w3.append(v[i])
    w0.sort(reverse=1)
    w1.sort(reverse=1)
    w2.sort(reverse=1)
    w3.sort(reverse=1)
    w0 = [0] + w0
    w1 = [0] + w1
    w2 = [0] + w2
    w3 = [0] + w3
    w0 = list(accumulate(w0))
    w1 = list(accumulate(w1))
    w2 = list(accumulate(w2))
    w3 = list(accumulate(w3))

    res = 0
    for i in range(len(w0)):
        for j in range(len(w1)):
            for k in range(len(w2)):
                for l in range(len(w3)):
                    if base*(i+j+k+l) + j + k*2 + l*3 <= W:
                        res = max(res, w0[i]+w1[j]+w2[k]+w3[l])
    print(res)

def __starting_point():
    main()
__starting_point()

from itertools import accumulate

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

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

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

acc = [[0] + list(accumulate(li)) for li in weights]

ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            for l, e4 in enumerate(acc[3]):
                if w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l <= W:
                    ans = max(ans, e1 + e2 + e3 + e4)

print(ans)


# https://atcoder.jp/contests/abc060/tasks/arc073_b
# 典型的なナップサック。だけど配列が大きいので素直に実装するとTLEになる
# 成約により、w1以上は必ず前のjを見ることに注意するとテーブルのサイズがぐっと減ることに気がつくがこれを実装するのはなかなかめんどくさそう。
# defaltdictを利用した再帰メモ化なら比較的実装可能では？

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


N, W = read_ints()
w, v = read_col(N, 2)

from collections import defaultdict
dp = defaultdict(lambda: -1)


def f(i, j):  # i番目を含んで考慮したとき重さjまでで達成できる価値の最大値
    if dp[i, j] != -1:
        return dp[i, j]
    if i == -1:
        return 0
    if j - w[i] < 0:
        return f(i - 1, j)

    ret = max(f(i - 1, j - w[i]) + v[i], f(i - 1, j))
    dp[i, j] = ret
    return ret


print((f(N - 1, W)))


def main():
    N, W = list(map(int, input().split()))
    WV = [tuple(map(int, input().split())) for _ in range(N)]
    cur = {0: 0}
    for w, v in WV:
        keys = sorted(list(cur.keys()), reverse=True)
        for k in keys:
            if k + w > W:
                continue
            cur[k + w] = max(cur[k] + v, cur.get(k + w, 0))
    return max(cur.values())

print((main()))


def main():
    N, W = list(map(int, input().split()))
    l = []
    w, v = list(map(int, input().split()))
    ww = w
    dp = [[[0] * (3*N) for _ in range(N+1) ]for _ in range(N)]
    dp[0][1][0] = v
    l.append((0, v))
    for _ in range(N-1):
        w, v = list(map(int, input().split()))
        l.append((w-ww, v))
    if W < ww:
        return 0
    for i in range(1, N):
        w, v = l[i]
        for j in range(1, N+1):
            for k in range(w):
                dp[i][j][k] = dp[i-1][j][k]
            for k in range(w, 3*N):
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
    r = 0
    for i in range(N+1):
        wt = W - i * ww
        if wt < 0:
            break
        r = max(r, max(dp[-1][i][:wt+1]))
    return r
print((main()))


import sys
input = sys.stdin.readline
n,w=list(map(int,input().split()))
w_sub,v_sub=list(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=list(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)


n,w=list(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)


N, W = list(map(int, input().split()))
wv = []

for _ in range(N):
    wv.append(tuple(map(int, input().split())))

# dp[i][j] i 番目まで、 重さ j で最大化した価値
# 答え: dp[N][W]
# 初期: dp[0][j] = 0
#       dp[i][0] = 0
#
# dp[i+1][j] = 品物i+1 を使わない場合、 dp[i][j]
#               品物i+1 を使う場合、 dp[i][j-w_{i+1}] + v_{i+1}
# i

memo = {}

def dfs(i, j):
    if (i,j) in memo:
        return memo[(i,j)]

    if i < 0 or j <= 0:
        return 0

    ret = 0
    wi, vi = wv[i]
    if j-wi < 0:
        ret = dfs(i-1, j)
    else:
        ret = max(dfs(i-1, j), dfs(i-1, j-wi) + vi)

    memo[(i,j)] = ret

    return ret

print((dfs(N-1, W)))


n,w=map(int,input().split())
kind=[[] for _ in range(4)]
for i in range(n):
    w_,v=map(int,input().split())
    if i==0:
        stan=w_
    kind[w_-stan].append(v)
for i in range(4):
    kind[i].sort(reverse=True)
    if len(kind[i])>=2:
        for j in range(len(kind[i])-1):
            kind[i][j+1]+=kind[i][j]
    kind[i]=[0]+kind[i]
ans=0
for i in range(len(kind[0])):
    for j in range(len(kind[1])):
        for k in range(len(kind[2])):
            for l in range(len(kind[3])):
                if stan*i+(stan+1)*j+(stan+2)*k+(stan+3)*l<=w:
                    ans=max(ans,kind[0][i]+kind[1][j]+kind[2][k]+kind[3][l])
print(ans)

from collections import defaultdict

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

dp = defaultdict(int)
dp[0] = 0

for w, v in wv:
    for k in sorted(list(dp.keys()), reverse=True):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)

ans = max(dp.values())
print(ans)


import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from bisect import bisect_right

def main():
    n,w = map(int,input().split())
    minw,u = map(int,input().split())
    item = {minw:[u],minw + 1:[],minw + 2:[], minw + 3:[]}
    for _ in range(n - 1):
        wei,u = map(int,input().split())
        item[wei].append(u)
    
    l = [0] * 4
    keys = sorted(item.keys())
    i = 0
    for k in keys:
        item[k].sort(reverse = True)
        l[i] = len(item[k])
        i += 1
    
    X = set()
    for i in range(l[0] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw][i - 1]
        cumsumx = cumsum
        for j in range(l[1] + 1):
            weight = minw * i + (minw + 1) * j 
            if j != 0:
                cumsumx += item[minw + 1][j - 1]
            if weight <= w:
                X.add((weight, cumsumx))

    Y = []
    for i in range(l[2] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw + 2][i - 1]
        cumsumy = cumsum
        for j in range(l[3] + 1):
            weight = (minw + 2) * i + (minw + 3) * j
            if j != 0:
                cumsumy += item[minw  + 3][j - 1]
            if weight <= w:
                Y.append((weight, cumsumy))
    
    Y.sort(key = lambda x:x[0])
    Yw = [0] * len(Y)
    cummax = [0] * len(Y)
    for i in range(len(Y)):
        if i == 0:
            cummax[i] = Y[i][1]
            Yw[i] = Y[i][0]
        else:
            cummax[i] = max(cummax[i - 1],Y[i][1])
            Yw[i] = Y[i][0]
    
    ans = 0
    for x in X:
        wei,va = x
        idx = bisect_right(Yw,w - wei)
        if idx == 0:
            continue
        else:
            ans = max(ans,cummax[idx - 1] + va)
    
    print(ans)
    
    
def __starting_point():
    main() 
__starting_point()

n,w=list(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)


n,w=list(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)


n,W=map(int,input().split())
w=[0 for i in range(n)]
v=[[] for i in range(4)]
dp=[[0] for i in range(4)]
for i in range(n):
  w[i],vi=map(int,input().split())
  v[w[i]-w[0]].append(vi)
for i in range(4):
  v[i].sort(reverse=True)
  for j in v[i]:
    dp[i].append(dp[i][-1]+j)
def dfs(i,cost):
  if cost>W:
    return -10**10
  elif i==4:
    return 0
  else:
    val=0
    for j in range(len(dp[i])):
      val=max(val,dp[i][j]+dfs(i+1,cost+j*(w[0]+i)))
    return val
print(dfs(0,0))

n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
from collections import Counter
w0=wv[0][0]
d={w0:[0],w0+1:[0],w0+2:[0],w0+3:[0],}
for w,v in wv:
  d[w].append(v)
for i in range(4):
  d[w0+i].sort(reverse=True)
sd={}
for i in range(4):
  tmp=0
  sd[w0+i]=[0]
  for v in d[w0+i]:
    tmp+=v
    sd[w0+i].append(tmp)
ans=0
for i in range(len(d[w0])):
  for j in range(len(d[w0+1])):
    for k in range(len(d[w0+2])):
      for l in range(len(d[w0+3])):
        if w0*i+(w0+1)*j+(w0+2)*k+(w0+3)*l<=W:
          ans=max(ans,sd[w0][i]+sd[w0+1][j]+sd[w0+2][k]+sd[w0+3][l])
print(ans)