#include <iostream>
#include <fstream>


using namespace std;

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

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


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;
    int t = 1;

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

    fout << m[1-t][g];
    return 0;
}