# 2维版本
#
# 1.状态定义 - dp[i][j] : 前i个物品容量为j的最大值
# 2.初始值 - dp[0][0] = 0
# 3.状态转移 - dp[i][j] = dp[i-1][j] if j < v[i]
# dp[i][j] = max(dp[i-1][j-v[i]] + w[i],dp[i-1][j]) if j >= v[i]
def main():
max_n,max_v = map(int,input().split())
v,w = [0]*(max_n+1),[0]*(max_n+1)
for i in range(1,max_n+1):
v[i],w[i] = map(int,input().split())
f = [[0 for i in range(max_v+1)] for j in range(max_n+1)]
for i in range(1,max_n+1):
for j in range(1,max_v+1):
if j < v[i]: f[i][j] = f[i-1][j] #容量为j时装不下第i个物品
else: f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i])
print(f[-1][-1])
# 1维版本,滚动数组
# 为什么可以使用滚动数组?
# - 在二维版本中dp[i][j]的值是由上轮dp[i-1]的状态得到的
# 1.状态定义 - dp[j]:容量为j时的最大值
# 2.初始值 - dp[0] = 0
def main():
max_n,max_v = map(int,input().split())
v,w = [0]*(max_n+1),[0]*(max_n+1)
for i in range(1,max_n+1):
v[i],w[i] = map(int,input().split())
f = [0] * (max_v + 1)
for i in range(1,max_n+1):
for j in range(max_v,v[i]-1,-1):
f[j] = max(f[j],f[j-v[i]]+w[i])
print(f[-1])
main()