#include <iostream>
#include <fstream>
using namespace std;
int w[5001],i,j,v[5001],n,g;
int a[5001][10001];
ifstream f("rucsac.in");
ofstream out("rucsac.out");
void citire(){
f>>n>>g;
for(i=1;i<=n;i++){
    f>>w[i]>>v[i];
}
f.close();
}
int main()
{citire();
for(i=1;i<=n;i++){
    for(j=0;j<=g;j++){
            a[i][j]=a[i-1][j];
        if(w[i] <= j)a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+v[i]);
    }
}
    out<<a[n][g];g.close();
    return 0;
}