#include <iostream>
#include <fstream>
using namespace std;

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

int N,G,D[10010],W[5010],P[5010];

int main()
{


    f>> N>>G;

    for(int i=1;i<=N;i++)
    {
     f>>W[i];
     f>>P[i];
    }

    for(int i=1;i<=N;i++)
    {
        for(int j=G-W[i];j>=0;j--)
            if(D[j]+P[i]>D[j+W[i]])
                 D[j+W[i]]=D[j]+P[i];
    }

    g<<D[G];

    return 0;
}