#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int d[2][10005],pr[5005],g[5005],n,gmax,lac,lop;
int main(){
    fin>>n>>gmax;
    for(int i=1;i<=n;i++)
    {
        fin>>g[i];
        fin>>g[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=gmax;j++)
        {
            lac=i%2;
            lop=1-lac;
            if(g[i]>j)
            d[lac][j]=d[lop][j];
            else
            d[lac][j]=max(d[lop][j],d[lop][j-g[i]]+pr[i]);
                }
    }
    fout<<d[n%2][gmax];
    return 0;
}