#include <bits/stdc++.h>

using namespace std;

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

const int CMAX = 30015;
int mat[CMAX][CMAX/2] , gm , pm , ob;

struct ex{
    int G , P;
}v[CMAX];

int main()
{
    fin >> ob >> gm;
    for(int i=1;i<=ob;i++)
    {
        fin >> v[i].G >> v[i].P;
    }
    for(int i=1;i<=ob;i++)
    {
        for(int j=1;j<=gm;j++)
        {
            if(v[i].G>j) mat[i][j] = mat[i-1][j];
            else mat[i][j] = max(mat[i-1][j] , mat[i-1][j-v[i].G] + v[i].P);
        }
    }

    /*
    for(int i=1;i<=ob;i++)
    {
        cout << i << " | ";
        for(int j=1;j<=gm;j++)
        {
            cout << mat[i][j] << " ";
        }
        cout << '\n';
    }
    */
    fout << mat[ob][gm];
    return 0;
}