#include <iostream>
#include <fstream>
#define MAXN 5001
using namespace std;

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

int n,G,best[2][10001],g[MAXN],c[MAXN];

inline int maxim(int a,int b)
{
    if(a>b)
    return a;
    return b;
}

int main()
{

    in>>n;
    in>>G;
    int i,j;
    for(i=1;i<=n;i++)
        in>>g[i]>>c[i];

    for(i=1;i<=n;i++)
        for(j=g[i];j<=G;j++)
            best[i%2][j]=maxim(best[(i-1)%2][j],best[(i-1)%2][j-g[i]]+c[i]);

    out<<best[n%2][G]<<"\n";
    return 0;
}