import numpy as np

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

# 持ち帰る最大値の重さまでのリストを作る。
# 持ち帰れる重さが10なら、添字が10までのリストを作る。
# 持ち帰る各重さ毎の最大値を持つ。
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    # dp[:W-w+1]+v
    # 次の品物を持ち帰っても重さの上限Wを超えない値以降だけを取得して、次の品物の価値を追加する
    # 持ち帰れる最大値-次の品物の重さしているので、同じ重さの品物が複数あった場合もより価値が高い方で比較される

    # dp[w:]
    # 現在の重さw以上の値を取得する

    # maximum(dp[:W-w+1]+v, dp[w:], out=dp[w:])
    # 2つの配列の要素を比較して、大きい方の要素を返す。
    # 次の品物を持ち帰った方が価値の総和が大きくなる場合は価値が更新される。
    w, v = map(int, input().split())
    np.maximum(dp[:W-w+1]+v, dp[w:], out=dp[w:])

print(dp[-1])
