#include <fstream>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int g[10005],profit[10005],dp[10005];
int main()
{
    long long n,G,maxi=0;
    in>>n>>G;
    dp[0]=0;
    for(int i=1;i<=n;i++)
        in>>g[i]>>profit[i];

    for(int i=1;i<=n;i++)
        for(int j=G;j>=0;j--)
        {
           if(dp[j]+profit[i]>=dp[g[i]+j] && j+g[i]<=G)
              dp[g[i]+j]=dp[j]+profit[i];
        }
    for(int j=G;j>=1;j--)
    {
        if(maxi<dp[j])
            maxi=dp[j];
    }
    out<<maxi;
    return 0;
}