#include<fstream>
using namespace std;
// int N,G,a[10100];
int N,G,a[16];

 int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int ii,j,greutate,castig;
    f>>N>>G;

    for(ii=1;ii<=N;ii++)
    {
        f>>greutate>>castig;
        for(j=G-greutate;j>=0;j--)
        {
            if(a[j+greutate]<a[j]+castig)
                a[j+greutate]=a[j]+castig;
        }
    }
    g<<a[G]<<'\n';
    return 0;
}
//4 7
//3 5
//2 3
//4 6
//3 9