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

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

int main()
{
    int N,G,D[10010],W[5010],P[5010];

    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;j>=0;j--)
            if(j-W[i]>=0)
              if(D[j-W[i]]+P[i]>D[j])

                 D[j]=D[j-W[i]]+P[i];
    }

    g<<D[G];

    return 0;
}