#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gmax,i,j,g[5001],v[5001],a[1001][10001];
int main()
{
    fin>>n>>gmax;
    for(i=1; i<=n; i++)
        fin>>g[i]>>v[i];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=gmax; j++)
           if(g[i]>j)
             a[i][j]=a[i-1][j];
            else
                a[i][j]=max(a[i-1][j],(v[i]+a[i-1][j-g[i]]));
    fout<<a[n][gmax];
}