from collections import defaultdict

N, W = [int(i) for i in input().split()]

Things = [[int(i) for i in input().split()] for j in range(N)]



dp = defaultdict(int)

dp[0] = 0

for w, v in Things:

    for nw, nv in list(dp.items()):

        if nw + w <= W:

            dp[nw + w] = max(dp[nw + w], nv + v)

print((max(dp.values())))
def d_knapsack1(N, W, Goods):

    """

    N個の品物のi番目について、重さはw_i, 価値はv_iである。

    品物のいくつかを選んでナップサックに入れるが、品物の重さの総和はW以下とする。

    品物の価値の総和の最大値を求めよ。

    ※ 1 <= w_i <= W <= 10^5 と、重さの制約がゆるめ

    """

    import numpy as np

    # dp[w]: 重さwの品物の入れ方で達成できる価値の最大値

    dp = np.zeros(W + 1, dtype=np.int64)

    for w, v in Goods:

        # 重さi(0<=i<=W-w)のときの価値に対し注目している荷物を入れて、

        # 重さi+wのときの価値を更新する

        np.maximum(dp[:W + 1 - w] + v, dp[w:], out=dp[w:])

        # outで指定した箇所のみ上書き。与えないと新しく配列が作られる

    return dp[-1]



N, W = [int(i) for i in input().split()]

Goods = [[int(i) for i in input().split()] for j in range(N)]

print((d_knapsack1(N, W, Goods)))
from collections import defaultdict

N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]
dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print((max(dp.values())))

def d_knapsack1(N, W, Goods):
    """
    N個の品物のi番目について、重さはw_i, 価値はv_iである。
    品物のいくつかを選んでナップサックに入れるが、品物の重さの総和はW以下とする。
    品物の価値の総和の最大値を求めよ。
    ※ 1 <= w_i <= W <= 10^5 と、重さの制約がゆるめ
    """
    import numpy as np

    # dp[w]: 重さwの品物の入れ方で達成できる価値の最大値
    dp = np.zeros(W + 1, dtype=np.int64)
    for w, v in Goods:
        # 重さi(0<=i<=W-w)のときの価値に対し注目している荷物を入れて、
        # 重さi+wのときの価値を更新する
        np.maximum(dp[: W + 1 - w] + v, dp[w:], out=dp[w:])
        # outで指定した箇所のみ上書き。与えないと新しく配列が作られる
    return dp[-1]


N, W = [int(i) for i in input().split()]
Goods = [[int(i) for i in input().split()] for j in range(N)]
print((d_knapsack1(N, W, Goods)))

-from collections import defaultdict +def d_knapsack1(N, W, Goods): +    """ +    N個の品物のi番目について、重さはw_i, 価値はv_iである。 +    品物のいくつかを選んでナップサックに入れるが、品物の重さの総和はW以下とする。 +    品物の価値の総和の最大値を求めよ。 +    ※ 1 <= w_i <= W <= 10^5 と、重さの制約がゆるめ +    """ +    import numpy as np + +    # dp[w]: 重さwの品物の入れ方で達成できる価値の最大値 +    dp = np.zeros(W + 1, dtype=np.int64) +    for w, v in Goods: +        # 重さi(0<=i<=W-w)のときの価値に対し注目している荷物を入れて、 +        # 重さi+wのときの価値を更新する +        np.maximum(dp[: W + 1 - w] + v, dp[w:], out=dp[w:]) +        # outで指定した箇所のみ上書き。与えないと新しく配列が作られる +    return dp[-1] + -Things = [[int(i) for i in input().split()] for j in range(N)] -dp = defaultdict(int) -dp[0] = 0 -for w, v in Things: -    for nw, nv in list(dp.items()): -        if nw + w <= W: -            dp[nw + w] = max(dp[nw + w], nv + v) -print((max(dp.values()))) +Goods = [[int(i) for i in input().split()] for j in range(N)] +print((d_knapsack1(N, W, Goods)))