#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int mat[5003][10003];

int main()
{
    int n, kg;
    fin>>n>>kg;

    int weight[5002], val[5002];
    for(int i=1; i<=n; i++)
        fin>>weight[i]>>val[i];

    int st[kg+1]={0};
    int sus[kg+1]={0};
    for(int i=1; i<=n; i++){

        for(int w=1; w<=kg; w++){

            st[w]=max(st[w-1], sus[w]);
            if(w>=weight[i])
                st[w]=max(val[i]+sus[w-weight[i]], st[w]);
            //cout<<st[w]<<" ";
        }

        //cout<<'\n';

        for(int j=1; j<=kg; j++)
            sus[j]=st[j];

    }

    fout<<sus[kg];

    return 0;
}