#include <iostream>
#include <stdio.h>

using namespace std;

int pret[5001],greutate[5001];
int optim[10001];

void rez()
{
    freopen("rucsac.in","r",stdin);
    int n,g;
    scanf("%d %d", &n, &g);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&greutate[i],&pret[i]);

    optim[0]=0;
    int ma=0;

    for(int i=1;i<=n;i++)
        for(int j=g-greutate[i];j>=0;j--)
            if(optim[j+greutate[i]]<optim[j]+pret[i])
            {
                optim[j+greutate[i]]=optim[j]+pret[i];
                if(optim[j+greutate[i]]>ma)
                    ma=optim[j+greutate[i]];
            }
    freopen("rucsac.out","w",stdout);
    printf("%d",ma);
}


int main()
{
    rez();
    return 0;
}