#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[DIM][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[i][j]=max(A[i-1][j],A[i-1][j-W[i]]+P[i]);
            else
                A[i][j]=A[i-1][j];
    for(int i=0;i<=g;i++)
        rez=max(rez,A[n][i]);
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}