# 与01背包问题的区别：每件物品可以选择无限次
# f[j]表示容积是j的话，最大的价值为多少

# 01背包：   f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)
# 完全背包： f[i][j] = max(f[i-1][j], f[i][j-v] + w)

N, V = map(int, input().split())
vlist, wlist = [0], [0]
for i in range(N):
    tmp = list(map(int, input().split()))
    vlist.append(tmp[0])
    wlist.append(tmp[1])

# 创建一维表
f = [0 for _ in range(V+1)]
for i in range(1, N+1):
    for j in range(1, V+1):
        if vlist[i] <= j:
            f[j] = max(f[j], f[j-vlist[i]]+wlist[i])
print(f[-1])

# 可以与01背包对比记忆
# 0 1 背包中，一维dp的方法中，容积j是倒序枚举
# 完全背包中，一维dp的方法中，容积j是正序枚举

# https://blog.csdn.net/yandaoqiusheng/article/details/84929357 枚举方向详解