#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n,g1,dp[2][10001];

struct ura
{
    int g,p;
}v[5001];

int main()
{
    cin>>n>>g1;
    for(int i=1;i<=n;i++)
        cin>>v[i].g>>v[i].p;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<v[i].g;j++)
            dp[i%2][j]=dp[(i-1)%2][j];
    for(int j=v[i].g;j<=g1;j++)
        dp[i%2][j]=max(dp[(i-1)%2][j-v[i].g]+v[i].p, dp[(i-1)%2][j]);
    }
     cout<<dp[n%2][g1];
    return 0;
}