#include <fstream>
#include <algorithm>


using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int a[5001][10001];
int main()
{
    int c[5001],g[10001],i,j,n,s;
    fin>>n>>s;
    for(i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=s;j++)
        {
            if(j>=g[i])
                a[i][j]=max(a[i-1][j-g[i]]+c[i],a[i-1][j]);
        }
    fout<<a[n][s];
    return 0;
}