#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1e3+5;
int v[maxn],w[maxn];//二维动态规划
int dp[maxn];//当前使用重量为j的最大价值
//注意：初始化很关键
//这里所有的位置都被初始化为0，所以dp[i]的含义变成了重量小于等于w[i]时的最大价值
//k<m时
//dp[k]=max_v;
//dp[0]=0  -->  f[w[0]]=v[0]  -->...
//dp[m-k]=0  -->  f[m-k+w[0]]=v[0]  -->...  相比较而言 不过是多了一个偏移量m-k
//所以不用去枚举所有质量啦，结果就是dp[c]
//而如果 最开始初始化成 dp[0]=0,dp[其他]=-inf
//则所有状态都将由dp[0][0]转移而来，最后就要for循环去找最大的dp[i]

//若题意变成了 重量恰好是c时的最大价值
//则初始化dp[0]=0,dp[i]=-inf,  最终结果就是dp[c]
int main()
{
    int n,c;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    cin>>w[i]>>v[i];

    for(int i=1;i<=n;i++)
        for(int j=c;j>=w[i];j--)//换一下 从大到小枚举，w[i]>0 则j-w[i]一定是没有被算过的，保证j-w[i]是i-1的 而不是i的
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }

   // cout<<dp[n][c]<<endl; 可以重量不达到c，也可以不装满所有n个物品，注意题目中的“前”
   //int ans=0;
   //for(int i=0;i<=c;i++)
   //ans=max(ans,dp[i]);//找出最大价值
   cout<<dp[c]<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1e4+5;
int v[maxn],w[maxn];//二维动态规划
int dp[maxn][maxn];//表示前i个物品，当前使用重量为j的最大价值
int main()
{
    int n,c;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=c;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(w[i]<=j)//要判断能不能装下
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
   // cout<<dp[n][c]<<endl; 可以重量不达到c，也可以不装满所有n个物品，注意题目中的“前”
   int ans=0;
   for(int i=0;i<=c;i++)
   ans=max(ans,dp[n][i]);//找出最大价值
   cout<<ans<<endl;
    return 0;
}