from collections import defaultdict



memo = {}

def dfs(i, w, l, W):

    if i >= len(l):

        return 0



    if (i, w) in memo:

        return memo[(i, w)]



    # not use

    ans = dfs(i + 1, w, l, W)



    # use

    if w + l[i][0] <= W:

        ans = max(ans, dfs(i + 1, w + l[i][0], l, W) + l[i][1])



    memo[(i, w)] = ans

    return ans





def main():

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

    l = []

    for _ in range(N):

        w, v = list(map(int, input().split()))

        l.append((w, v))

    print((dfs(0, 0, l, W)))





if __name__ == '__main__':

    main()

from collections import defaultdict, Counter

from itertools import product, groupby, count, permutations, combinations

from math import pi, sqrt

from collections import deque

from bisect import bisect, bisect_left, bisect_right

from string import ascii_lowercase

from functools import lru_cache

import sys

sys.setrecursionlimit(10000)

INF = float("inf")

YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"

dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]

dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]





def inside(y, x, H, W):

    return 0 <= y < H and 0 <= x < W





def ceil(a, b):

    return (a + b - 1) // b





def dfs(i, ws, d, W):

    if i >= len(ws):

        return 0

    w = ws[i]



    ans = dfs(i + 1, ws, d, W)

    total = 0

    for j in range(len(d[w])):

        total += d[w][j]

        if (j + 1) * w <= W:

            ans = max(ans, dfs(i + 1, ws, d, W - (j + 1) * w) + total)

    return ans





def main():

    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 w in list(d.keys()):

        d[w].sort(reverse=True)



    print((dfs(0, list(d.keys()), d, W)))





if __name__ == '__main__':

    main()

from collections import defaultdict

memo = {}


def dfs(i, w, l, W):
    if i >= len(l):
        return 0
    if (i, w) in memo:
        return memo[(i, w)]
    # not use
    ans = dfs(i + 1, w, l, W)
    # use
    if w + l[i][0] <= W:
        ans = max(ans, dfs(i + 1, w + l[i][0], l, W) + l[i][1])
    memo[(i, w)] = ans
    return ans


def main():
    N, W = list(map(int, input().split()))
    l = []
    for _ in range(N):
        w, v = list(map(int, input().split()))
        l.append((w, v))
    print((dfs(0, 0, l, W)))


if __name__ == "__main__":
    main()

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys

sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def dfs(i, ws, d, W):
    if i >= len(ws):
        return 0
    w = ws[i]
    ans = dfs(i + 1, ws, d, W)
    total = 0
    for j in range(len(d[w])):
        total += d[w][j]
        if (j + 1) * w <= W:
            ans = max(ans, dfs(i + 1, ws, d, W - (j + 1) * w) + total)
    return ans


def main():
    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 w in list(d.keys()):
        d[w].sort(reverse=True)
    print((dfs(0, list(d.keys()), d, W)))


if __name__ == "__main__":
    main()

-from collections import defaultdict +from collections import defaultdict, Counter +from itertools import product, groupby, count, permutations, combinations +from math import pi, sqrt +from collections import deque +from bisect import bisect, bisect_left, bisect_right +from string import ascii_lowercase +from functools import lru_cache +import sys -memo = {} +sys.setrecursionlimit(10000) +INF = float("inf") +YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no" +dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0] +dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1] -def dfs(i, w, l, W): -    if i >= len(l): +def inside(y, x, H, W): +    return 0 <= y < H and 0 <= x < W + + +def ceil(a, b): +    return (a + b - 1) // b + + +def dfs(i, ws, d, W): +    if i >= len(ws): -    if (i, w) in memo: -        return memo[(i, w)] -    # not use -    ans = dfs(i + 1, w, l, W) -    # use -    if w + l[i][0] <= W: -        ans = max(ans, dfs(i + 1, w + l[i][0], l, W) + l[i][1]) -    memo[(i, w)] = ans +    w = ws[i] +    ans = dfs(i + 1, ws, d, W) +    total = 0 +    for j in range(len(d[w])): +        total += d[w][j] +        if (j + 1) * w <= W: +            ans = max(ans, dfs(i + 1, ws, d, W - (j + 1) * w) + total) -    l = [] +    d = defaultdict(list) -        l.append((w, v)) -    print((dfs(0, 0, l, W))) +        d[w].append(v) +    for w in list(d.keys()): +        d[w].sort(reverse=True) +    print((dfs(0, list(d.keys()), d, W)))