#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n, G, i, j, d[10001], g[5001], v[5001], Max;
int main ()
{
    fin>>n>>G;
    for (i=1; i<=n; i++)
        fin>>g[i]>>v[i];
    for (i=1; i<=n; i++)
            d[i]=-1;
    for (i=1; i<=n; i++)
        for (j=G-g[i]; j>=0; j--)
            if (d[j]+1) d[j+g[i]]=max(d[j+g[i]], d[j]+v[i]);
    for (i=1; i<=G; i++)
        if (d[i]>Max)
            Max=d[i];
    fout<<Max;
}