#include <fstream>
#include<algorithm>

#define m_max 10010
#define n_max 5010
using namespace std;
ifstream f("rucsac.in");
ofstream gout("rucsac.out");
int n,g,G[n_max],P[n_max],Sol[m_max];
int main()
{

    f>>n>>g;
    for(int i=1; i<=n; i++)
        f>>G[i]>>P[i];
    for(int i=1; i<=n; i++)
        for(int j=g; j>=G[i]; j--)
            Sol[j]=max(Sol[j],Sol[j-G[i]]+P[i]);
    gout<<Sol[g];

}