#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,i,j,gmax,dp[3][10002],x,y;
int last,curent;
struct ha
{
    int val; int g;
} v[5002];
int main()
{
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].g>>v[i].val;
    }
    ///dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i].val]
    last=1;
    curent=2;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=gmax;j++)
        {
            if((j-v[i].g>=0) and dp[last][j-v[i].g]>=0) dp[curent][j]=max(dp[last][j],dp[last][j-v[i].g]+v[i].val);
            else dp[curent][j]=dp[last][j];
        }
        swap(curent,last);
    }
    /*for(i=1;i<=2;i++)
    {
        for(j=1;j<=gmax;j++) cout<<dp[i][j]<<' ';
        cout<<'\n';
    }*/
    fout<<dp[last][gmax];
    return 0;
}