#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];
int main()
{fin>>n>>g;
for(int i=1; i<=n; i++)
fin>>a[i]>>b[i];
for(int i=1; i<=n; i++)
{int l=i%2;
int L=1-l;
for(int j=0;j<=g;j++)
{c[l][j]=c[L][j];
if(a[i]<=j)
c[l][j]=max(c[L][j],c[L][j-a[i]]+b[i]);
}
}
fout<<c[n%2][g];
return 0;
}