#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,a[5010],b[5010],c[10001][10001],pmax;
int main()
{fin>>n>>g;
for(int i=1; i<=n; i++){
fin>>a[i]>>b[i];
}
for(int i=1; i<=n; i++)
{for(int j=0; j<=g; j++)
{c[i][j]=c[i-1][j];
if(a[i]<=j)
c[i][j]=max(c[i][j],c[i-1][j-a[i]]+b[i]);
}
}
pmax=c[n][g];
fout<<pmax;
return 0;
}