#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,i,G,maxim,w[5001],p[5001],j;
int a[10001][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][j]=a[i-1][j];
            else
                a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+p[i]);
            if(a[i][j]>maxim)
                maxim=a[i][j];
        }
    fout<<maxim;
}