#include <iostream>
#include <fstream>


using namespace std;

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

int v[10000];
int w[10000];
int m[2][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%2][j] = max(m[(i-1)%2][j-w[i]] + v[i],m[(i-1)%2][j]);
            else
                m[i%2][j] = m[(i-1)%2][j];

    cout << m[n%2][g];
    return 0;
}