#include <fstream>
#define nmax 10010
using namespace std;

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

int g[nmax/2],p[nmax/2];
int d[nmax][nmax/2];

int main()
{
    int n,gr,i,j;
    fin>>n>>gr;
    for(i = 1; i <= n; i++){
        fin>>g[i];
        fin>>p[i];
    }

    for(i = 1; i <= n; i++){
        for(j = 1; j <= gr; j++){
            d[i][j] = d[i-1][j];
            if(j >= g[i]){
                d[i][j] = max(d[i][j],(d[i-1][j-g[i]])+ p[i]);
            }
        }
    }
    fout<<d[n][gr];
}