#include <iostream>
#include <fstream>
using namespace std;
ifstream Gigi ("rucsac.in");
ofstream Marcel ("rucsac.out");
int m[2][10001];

int main()
{
    int i,j,n,g;
    bool b=0;
    Gigi>>n>>g;
    int v[n];
    int w[n];
    for (i=0;i<n;i++){
        Gigi>>w[i]>>v[i];
    }
    for (i=0;i<n;i++,b=1-b){
        for (j=0;j<=g;j++){
            m[1-b][j]=m[b][j];
            if (w[i]<=j){
                m[1-b][j]=max(m[1-b][j],m[b][j-w[i]]+v[i]);
            }
        }
    }
    Marcel<<m[b][g];
    return 0;
}