#include <iostream>
#include <fstream>

using namespace std;

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

struct obiect
{
    int g, v;
};
int main()
{
    int n, G;
    cin>>n>>G;
    obiect ob[5001];
    for(int i=1; i<=n; i++)
        cin>>ob[i].g>>ob[i].v;
    int mat[n+1][G+1];
    for(int i=0; i<=n; i++)
        mat[i][0]=0;
    for(int j=0; j<=G; j++)
        mat[0][j]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=G;j>=1;j--)
        {
            if(j-ob[i].g<0)
                mat[i][j]=0;
            else
            {
                mat[i][j]=max(mat[i-1][j], mat[i-1][j-ob[i].g]+ob[i].v);
            }
        }

    }
    cout<<mat[n][G];
    return 0;
}