#include <fstream>
#include <bits/stdc++.h>
using namespace std;
FILE* f=fopen("rucsac.in","r");
FILE* g=fopen("rucsac.out","w");
int n,i,go,po,j,max1,G;
int dp[2][10001];
int main()
{
    fscanf(f,"%d%d",&n,&G);
    dp[0][0]=1;
    for(i=1; i<=n; ++i)
    {

        fscanf(f,"%d%d",&go,&po);
        for(j=G; j>=0; --j)
        {
            dp[i%2][j]=dp[(i-1)%2][j];
            if(j-go>=0 && dp[(i-1)%2][j-go]!=0)
                dp[i%2][j]=max(dp[i%2][j],po+dp[(i-1)%2][j-go]);
        }
    }
    for(j=0;j<=G;j++)
    {
        if(max1<dp[n%2][j])
            max1=dp[n%2][j];
    }
    fprintf(g,"%d",max1-1);
    return 0;
}