'''
完全背包实现，优化解法，时间复杂度是O(N^2)状态转移
dp(i, j)表示前i个物品在容量是j的情况下的最大总价值cost[i] 表示物品开销
val[i] 表示物品价值dp(i, j) = max ( dp(i-1, j), dp(i, j-cost[i]) + val[i] )'''n, v = map(int, input().split())arr = []
for _ in range(n):a, b = map(int, input().split())arr.append((a, b))# arr.sort() # 是否排序似乎影响不是很大
dp = [0] * (v + 1)
for i in range(n):for j in range(v + 1):if i == 0:dp[j] = (j // arr[i][0]) * arr[i][1]else:# 此时dp[j] 表示的是前i-1个物品在容量为j的条件下的最大总价值，其实就是第i个物品选0个情况下的dp(i, j)的以第一个候选值# 下面第i个物品拿掉一个就行了，不用枚举拿多个的不同情况if j >= arr[i][0]:# 前i个物品总容量是dp[j], dp[j-arr[i][0]]情况下的最大价值和再加上单独个拿掉的那个i物品的价值dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1])print(dp[v])