#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int W[50], V[50];//greutatea si castigul fiecarui obiect
int D[50][100];
//D[i][j] cel mai bun castig pentru primele i obiecte avand greutatea insumata j
int main()
{
    int N,G,P;
    fin>>N>>G;
    for (int i = 1; i <= N; ++i)
    {
        fin>>W[i]>>V[i];
    }
    //CASTIGUL MAXIM OBTINUT
    for( int j = G; j >= 0;j--)
    D[0][j]=0;
    for( int i = 1; i <= N; i++)
    D[i][0]=0;
    for( int i = 1; i <= N; i++)
        for( int j =0; j<= G;j++)
        if(W[i]>j)
        D[i][j]=D[i-1][j];
        else
            if( D[i-1][j] < D[i-1][j-W[i]] + V[i] )
                D[i][j] = D[i-1][j-W[i]] + V[i];//adaug obiectul i
            else
                D[i][j]=D[i-1][j];//nu adaug obiectul i
    P=D[N][G];
    fout<<P;
    return 0;
}