首先介绍一下背包问题的思路
定义数组dp[v]：对于一个体积为v的背包，dp[v]表示的是花费空间为v的最大解，0表示不能花费体积为v的空间
定义物品价值数组jz[n]，jz[n]表示第n个物品的价值
定义物品体积数组tj[n]，tj[n]表示第n个物品的体积

算法过程：
1.来一个物品，能放进背包就放进去，不能放进去直接丢掉
2.对于第一步不能丢的物品，判断它能否取代背包里已有的物品，如果能，则更新每一个使用到该物品的dp数组，设已使用空间为f(2)
3.对于第二步更新完的策略，原取代物品（或者是新来的物品）仍有可能可以继续放在背包内（只要不超过背包最大容量），可以组成新的方案，因此需要拓展方案，拓展范围是dp[0] - dp[f(2)]，背包的使用空间从f(2)过渡到f(3)
4.继续放入物品，直到没有物品可以被选择，此时已经得到每一个体积v对应的最大价值，但是空间仍有可能有剩余，所以max(dp)是体积v能放下的最大价值，dp[-1]是刚好体积v的最大价值

n, v = (int(x) for x in input().split())
tj = []
jz = []
for i in range(n):
    t, j = (int(x) for x in input().split())
    tj.append(t)
    jz.append(j)
dp = [0 for i in range(v+1)]
for i in range(n):  # i表示向背包内放入第i个物体
    if tj[i] > v:
        continue
    dp_copy = dp.copy()  # 必须要拷贝数组，防止在原dp数组上重复累加
    for j in range(v+1):  # j表示背包体积
        if dp[j] and j + tj[i] <= v:  # 如果体积j有解并且能放下当前物品
            dp_copy[j + tj[i]] = max(dp[j + tj[i]], dp[j] + jz[i])  # 更新物品放置策略（此时放进背包）
    dp_copy[tj[i]] = max(dp[tj[i]], jz[i])  # 更新体积tj[i]的解
    dp = dp_copy
# print(dp)
print(max(dp))
print(dp[-1])