#include <fstream>

using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int g[5001], p[5001];
int dp[1001];
int main()
{
    int n, G, i, j, maxx=0;
    cin>>n>>G;
    for (i=1;i<=n;i++)
    {
        cin>>g[i]>>p[i];
    }
    dp[0]=0;
    for (i=1;i<=n;i++)
    {
    for (j=G-g[i];j>=0;j--)
    {
        if (dp[j+g[i]]<dp[j]+p[i])
        {
            dp[j+g[i]]=dp[j]+p[i];
            maxx=max(maxx, dp[j+g[i]]);
        }
    }
    }
    cout<<maxx;
    return 0;
}