#include <stdio.h>
typedef struct  
{
    int greutate, profit;
}obiect;
obiect v[5000];
int dp[10000]={0};
int main()
{
    int n, G;
    FILE *fin=NULL;
    fin=fopen("rucsac.in","r");
    FILE *fout=NULL;
    fout=fopen("rucsac.out","w");
    fscanf(fin,"%d %d",&n,&G);
    for(int i=0;i<n;i++)
    {
        fscanf(fin,"%d %d",&v[i].greutate,&v[i].profit);
    }
    fclose(fin);
    for(int i=0;i<n;i++)
    {
        for(int g=G;g>=v[i].greutate;g--)
        {
            if(dp[g]<dp[g-v[i].greutate]+v[i].profit)
            {
                dp[g]=dp[g-v[i].greutate]+v[i].profit;
            }
        }
    }
    int Pmax = 0;
    for(int g=0;g<=G;g++)
    {
        if(dp[g]>Pmax)
            Pmax=dp[g];
    }
    
    fprintf(fout,"%d\n",Pmax);
    fclose(fout);
    return 0;
}