#include <iostream> ///dp[i][j] = costul maxim pentru obiectele 1...i si greutatea j
#include <fstream>  ///facem in n*gmax
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,i,j,dp[3][10005],last,curent,weight,gmax;
struct ha
{
    int val; int g;
} v[5005];
int main()
{
    fin>>n>>gmax;
    for(i=1;i<=n;i++) fin>>v[i].g>>v[i].val;
    last=1; curent=2; ///ne trebuie doar 2 coloane
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=v[i].g-1;j++) dp[curent][j]=dp[last][j];
        for(j=v[i].g;j<=gmax;j++)
        {
            dp[curent][j]=max(dp[last][j],dp[last][j-v[i].g]+v[i].val);
        }
        swap(curent,last);
    }
    fout<<dp[last][gmax];
    return 0;
}