#include <fstream>
using namespace std;

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

int n,g,v[5005],w[5005],m[100005];

void citire(){
    fin>>n>>g;
    for (int i=1;i<=n;i++)
        fin>>w[i]>>v[i];
}

int rucsac(int n,int g){
    int i,j;
    for (i=1;i<=n;i++)
        for (j=g;j>=1;j--)
            if (j>=w[i] && m[j]<v[i]+m[j-w[i]])
                m[j]=v[i]+m[j-w[i]];
    return m[g];
}

int main(){
    citire();
    fout<<rucsac(n,g);
    fin.close();
    fout.close();
    return 0;
}