def get_max_value_v1(v_arr, w_arr, V):
    """
        完全背包问题, 动态规划
        - dp[i, j] 代表考虑第i个元素且背包容量为j时最大的重量
        - 状态转移方程：
        -   dp[i][j] = max(dp[i-1][j], dp[i-1][j-n*v[i] + n*w[i]) if j-n*v[i]>0
        -   说明：数量无限的情况下，可以考虑放入n个i元素

    这样居然会超时，由后往前计算时，出现了重复计算
    """
    dp = [0] * (V + 1)
    for i in range(len(v_arr)):
        for j in range(V, -1, -1):
            n = 1
            while j - n * v_arr[i] >= 0:
                dp[j] = max(dp[j], dp[j - n * v_arr[i]] + n * w_arr[i])
                n += 1
    return dp[V]

def get_max_value_v2(v_arr, w_arr, V):
    """
        完全背包问题，用空间换时间版本
        dp[i][j] = max(dp[i-1][j], dp[i][j-v[i] + w[i]) if j-v[i]>0
    """
    n = len(v_arr)
    dp = [[0] * (V + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(V + 1):
            if j - v_arr[i - 1] >= 0:
                dp[i][j] = max(dp[i][j - v_arr[i - 1]] + w_arr[i - 1], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][V]


if __name__ == '__main__':
    N, V = map(int, input().split())
    v_arr, w_arr = list(), list()
    for _ in range(N):
        v, w = map(int, input().split())
        v_arr.append(v)
        w_arr.append(w)
    max_value = get_max_value_v2(v_arr, w_arr, V)
    print(max_value)