#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
short n,i,G,w[10001],p[5001],j;
int maxim,a[2][10001];
int main(){
    fin>>n>>G;
    for(i=1;i<=n;i++){
        fin>>w[i]>>p[i];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=G;j++){
            if(w[i]>j)
                a[i%2][j]=a[(i-1)%2][j];
            else
                a[i%2][j]=max(a[(i-1)%2][j],a[(i-1)%2][j-w[i]]+p[i]);
            if(a[i%2][j]>maxim)
                maxim=a[i%2][j];
        }
    fout<<maxim;
}