#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,i,w[5001],p[5001],d[2][10001],gr,l,grc,l2;

int main() {
    f >> n >> gr;
    for (i=1;i<=n;i++)
        f >> w[i] >> p[i];
    d[0][w[1]]=p[1];
    for (i=2;i<=n;i++) {
        if (i%2==0) {l=1;l2=0;}
               else {l=0;l2=1;}
        for (grc=1;grc<=gr;grc++)
            if (grc>=w[i]) d[l][grc]=max(d[l2][grc],d[l2][grc-w[i]]+p[i]);
                else d[l][grc]=d[l2][grc];
    }
    g << d[1][gr] << '\n';
    f.close();g.close();
    return 0;
}