#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream p("rucsac.out");
long long a[5001][5001],gmax,g[1001],val[1001],i,j;
int n;
int main()
{
    f>>n>>gmax;
for(i=1;i<=n;i++)
    f>>g[i]>>val[i];
for(i=1;i<=n;i++)
{for(j=1;j<=gmax;j++)
if(g[i]>j)
    a[i][j]=a[i-1][j];
else
a[i][j]=max(a[i-1][j],a[i-1][j-g[i]]+val[i]);

}
p<<a[n][gmax];
    return 0;
}