#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int r[100][100],w[100],p[100];
int main()
{
    int i,n,g,j;
    f>>n>>g;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
    for(i=1;i<=n;i++)
            for(j=1;j<=g;j++)
    {
        if(w[i]<=j)
            r[i][j]=max(r[i-1][j],(r[i-1][j-w[i]]+p[i]));
            else r[i][j]=r[i-1][j];
    }
    g<<r[n][g];
}