#include <iostream>
#include <fstream>


using namespace std;

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

int v[10000];
int w[10000];
int m[10001][5001];


int main()
{
    int n,g,i,j;
    fin >> n >> g;
    for(i=1;i<=n;++i)
        fin >> w[i] >> v[i];

    for(j=0;j<=g;++j)
        m[0][j] = 0;


    for(i=1;i<=n;++i)
    for(j=0;j<=g;++j)
            if(j >= w[i])
                m[i][j] = max(m[i-1][j-w[i]] + v[i],m[i-1][j]);
            else
                m[i][j] = m[i-1][j];

    fout << m[n][g];
    return 0;
}