#include <iostream>
#include <stdio.h>
using namespace std;

int N,G;
struct obiect
{
    int W,P;
    float eff;
};
obiect a[5000];
int maxim(int a,int b)
{
    if(a>b)return a;
    else return b;
}
void citire()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);


    scanf("%d%d",&N,&G);
    for (int i = 1; i <= N; ++i)
    {

        scanf("%d%d",&a[i].W,&a[i].P);
        a[i].eff=(float)a[i].P/a[i].W;

    }
}
int m[100][100];
void dp()
{
    int i,j;
    for(i=1; i<=N; i++)
        for(j=1; j<=G; j++)
            if(a[i].W==j || m[i-1][j-a[i].W]!=0)
                m[i][j]=maxim(m[i-1][j],m[i-1][j-a[i].W]+a[i].P);
            else m[i][j]=m[i-1][j];
}
int main()
{
    citire();

    dp();

    cout<<m[N][G];

    return 0;
}