#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,m,gr[5001],p[5001],dp[5001][10001];
void citire()
{
    f>>n>>m;
    for(int i=0;i<n;i++)
    {
        f>>gr[i];
        f>>p[i];
    }
}
void greutati()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<gr[i]-1;j++)
            dp[i][j]=dp[i-1][j];
        for(int j=gr[i];j<=m;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-gr[i]]+p[i]);
        }
    }
}
int main()
{
    citire();
    greutati();
    g<<dp[n-1][m];
    return 0;
}