#include <fstream>
using namespace std;
int d[10001];
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,G,g,p,dr=0,maxx=0;
    cin>>n>>G;
    d[0]=1;
    for(int T=1;T<=n;T++)
    {
        cin>>g>>p;
        for(int i=min(dr,G-g);i>=0;i--)
            if(d[i])
                d[i+g]=max(d[i]+p,d[i+g]);
        dr=min(G,dr+g);
    }
    maxx=d[G];
    for(int i=G-1;i>0;i--)
        maxx=max(maxx,d[i]);
    cout<<maxx-1;
    return 0;
}