#include <fstream>
#include <iostream>
#define DIM 5001
#define GMAX 10001
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g,W[DIM],P[DIM];
int A[GMAX];
int rez;
int main()
{
    fi>>n>>g;
    for(int i=1;i<=n;i++)
        fi>>W[i]>>P[i];
    for(int i=1;i<=n;i++)
        for(int j=g;j>=0;j--)
            if(j>=W[i])
                A[j]=max(A[j],A[j-W[i]]+P[i]);
            else
                A[j]=A[j];
    for(int i=0;i<=g;i++)
        rez=max(rez,A[i]);
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}